Here are the maximum number of steps required through 10, and likely maximum number of steps required through 12:
6: 14 7: 26 8: 74 9: 86 10: 126 11: 106 (?) (full state space not explored) 12: 130 (?) (full state space not explored)
Here's a puzzle game. I call it Reverse the List of Integers
171–180 of 188 posts
Re: Here's a puzzle game. I call it Reverse the List of Integers
#172Earlier quoted context omitted.
In Towers of Hanoi, you're only allowed to pick up one disc at a time, so it's not completely trivial. It's simply operation intensive... kinda like Reverse the List of Integers [1] https://en.wikipedia.org/wiki/Tower_of_Hanoi
They're not suggesting picking up multiple discs at a time: [3,2,1][][] => [3,2][][1] => [3][][1,2] => [][][1,2,3] In effect, they're just observing that the algorithm "while x := A.pop(): B.push(x)" reverses A onto B.
Of course I'm suggesting picking up multiple discs at a time. That's the whole idea.
Compare thih9's comment:
> Like tower of hanoi[1], but you can add or remove empty pegs, blocks are the same size and can be stacked in any order, you can move as many blocks as you want and you cannot have towers with the same amount of blocks.
All my comment did was to point out that this description doesn't work, because the rules here are not similar to the rules of Towers of Hanoi.
Under the rules of the original comment, here's how you reverse the list [7, 5, 3]:
+++++++ +++++ +++
+++(----) +++++ +++(++++)
Re: Here's a puzzle game. I call it Reverse the List of Integers
#173Earlier quoted context omitted.
Keeping the intermediate results of computations is just called programming. They go into a variable or a data structure like a vector or a hash map.
That tends to blow up your memory. And even if you have huge amounts of memory available, using a big cache will slow down your program enormously.
You: Dynamic programming means saving the results of computations
Me: That's just normal programming, there is no reason to use a term that someone made up in the 60s to as intentionally nonsensical.
You: That will blow up your memory and slow down your program!
What are you talking about here? All I said was that what you described was normal programming. I didn't come up with anything different, we're still talking about whatever you wrote. Somehow now storing data, something that happens in every program ever made, 'blows up memory'.
Re: Here's a puzzle game. I call it Reverse the List of Integers
#174Earlier quoted context omitted.
That tends to blow up your memory. And even if you have huge amounts of memory available, using a big cache will slow down your program enormously.
You: Dynamic programming means saving the results of computations Me: That's just normal programming, there is no reason to use a term that someone made up in the 60s to as intentionally nonsensical. You: That will blow up your memory and slow down your program! What are you talking about here? All I said was that what you described was normal programming. I didn't come up with anything different, we're still talking…
But there is a difference between memoization and dynamic programming. Memoization or otherwise indiscriminately storing the results of computations will blow up your memory use on many problems, where a dynamic programming approach would not.
Dynamic programming does not mean saving the results of computations, it is about saving the _minimal_ number of results, without having to recompute already solved subproblems later on.
I agree that the name chosen is nonsensical, but the concept is very much a real thing. And a quite important one at that.
Re: Here's a puzzle game. I call it Reverse the List of Integers
#175Here are the maximum number of steps required through 10, and likely maximum number of steps required through 12: 6: 14 7: 26 8: 74 9: 86 10: 126 11: 106 (?) (full state space not explored) 12: 130 (?) (full state space not explored)
Finished with a full state-space search of 11; worst case is indeed 106 (vs 126 for 10).
Re: Here's a puzzle game. I call it Reverse the List of Integers
#176Earlier quoted context omitted.
You: Dynamic programming means saving the results of computations Me: That's just normal programming, there is no reason to use a term that someone made up in the 60s to as intentionally nonsensical. You: That will blow up your memory and slow down your program! What are you talking about here? All I said was that what you described was normal programming. I didn't come up with anything different, we're still talking…
But there is a difference between memoization and dynamic programming. Memoization or otherwise indiscriminately storing the results of computations will blow up your memory use on many problems, where a dynamic programming approach would not. Dynamic programming does not mean saving the results of computations, it is about saving the _minimal_ number of results, without having to recompute already solved subproblems…
Your previous comment: dynamic programming will keep around previous subproblem solutions
Your comment here: Dynamic programming does not mean saving the results of computations
indiscriminately storing the results of computations
This is not something that happens. No is out there storing a bunch of stuff they don't need on purpose, running out of memory, then calling it a day. That's like saying "some people walk straight into walls, but in dynamic walking we go around walls!".
it is about saving the _minimal_ number of results, without having to recompute already solved subproblems later on.
Again, this is just what programming is some times. You save results instead of recomputing stuff.
Re: Here's a puzzle game. I call it Reverse the List of Integers
#177Earlier quoted context omitted.
None of the implementations support negative numbers, but the rules say integer which includes negative numbers, so that should be a legal move.
Negative numbers would break the game by making the number of possible splits infinite. E.g. 1 could split into [-2, 3], [-3, 4], [-4, 5], etc. It also violates Rule 1 because one of the splits is larger than the original number.
You're right in the first sentence, but you're second sentence if we're talking about splitting the largest original number itself that way.
Re: Here's a puzzle game. I call it Reverse the List of Integers
#178Earlier quoted context omitted.
You: Dynamic programming means saving the results of computations Me: That's just normal programming, there is no reason to use a term that someone made up in the 60s to as intentionally nonsensical. You: That will blow up your memory and slow down your program! What are you talking about here? All I said was that what you described was normal programming. I didn't come up with anything different, we're still talking…
But there is a difference between memoization and dynamic programming. Memoization or otherwise indiscriminately storing the results of computations will blow up your memory use on many problems, where a dynamic programming approach would not. Dynamic programming does not mean saving the results of computations, it is about saving the _minimal_ number of results, without having to recompute already solved subproblems…
Yep, it has a nonsensical name, that's the point I wanted to convey.
Actual "dynamic programming" would be self-modifying code, or something just as sophisticated, IMO. Or Prolog =)
What about "memoization optimized backtracking"?
Re: Here's a puzzle game. I call it Reverse the List of Integers
#179Here are the maximum number of steps required through 10, and likely maximum number of steps required through 12: 6: 14 7: 26 8: 74 9: 86 10: 126 11: 106 (?) (full state space not explored) 12: 130 (?) (full state space not explored)
Finished with a full state-space search of 11; worst case is indeed 106 (vs 126 for 10).
Finished with a full-state search of 12; worst case is indeed 130. Found a game for n=14 that takes 172 moves: 6 11 8 2 7 10 9 12 4 1 14 3.
Re: Here's a puzzle game. I call it Reverse the List of Integers
#180Earlier quoted context omitted.
But there is a difference between memoization and dynamic programming. Memoization or otherwise indiscriminately storing the results of computations will blow up your memory use on many problems, where a dynamic programming approach would not. Dynamic programming does not mean saving the results of computations, it is about saving the _minimal_ number of results, without having to recompute already solved subproblems…
Yep, it has a nonsensical name, that's the point I wanted to convey. Actual "dynamic programming" would be self-modifying code, or something just as sophisticated, IMO. Or Prolog =) What about "memoization optimized backtracking"?
I'd propose "Minimal memory optimal subproblem iteration"? Or "minimem iteration" for the friends?
I don't like mentioning memoization in DP's name, as I have had a lot of problems explaining students how you go beyond the memoization approach.