Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Here's a puzzle game. I call it Reverse the List of Integers

mathstodon.xyz

Post reply on HN
Print view View original

181–188 of 188 posts

Re: Here's a puzzle game. I call it Reverse the List of Integers

#181

Post by 317070 »

CyberDildonics wrote: post #176
317070 wrote: post #174

Earlier 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…

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 s…

> No is out there storing a bunch of stuff they don't need on purpose, running out of memory, then calling it a day.

There are a lot of people (such as my students) that would take a DP problem, solve with recursion, throw some caching [0] in and call it a day. They are often surprised by the 1000x speedups using a DP algorithm instead, no caching needed.

[0] https://docs.python.org/3/library/functools.html#functools.c...

> Again, this is just what programming is some times. You save results instead of recomputing stuff.

I'm sorry, but I still don't get the argument you are making. That DP is part of programming? Well, yes?

Re: Here's a puzzle game. I call it Reverse the List of Integers

#182

Post by CyberDildonics »

317070 wrote: post #181
CyberDildonics wrote: post #176

Earlier quoted context omitted.

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 s…

> No is out there storing a bunch of stuff they don't need on purpose, running out of memory, then calling it a day. There are a lot of people (such as my students) that would take a DP problem, solve with recursion, throw some caching [0] in and call it a day. They are often surprised by the 1000x speedups using a DP algorithm instead, no caching needed. [0] https://docs.python.org/3/library/functools.html#functools…

That DP is part of programming?

Dynamic programming was a made up nonsense term from the 50s to be opaque and vague so they wouldn't be bothered. It doesn't mean anything, but people try to make up some backwards rationalization.

Computing a factorial by recursively computing all the other previous factorials if you have any of them already done is an insane way to work. Doing something straightforward and sane like saving some results is like walking on broken glass then calling putting something over your feet "shoe walking". There is no special fancy label for doing the simple sane version of something.

Re: Here's a puzzle game. I call it Reverse the List of Integers

#183

Post by 61u »

OskarS wrote: post #146

Neat little problem! You could do SAT-solvers and stuff, but it's also obviously a graph search problem: each state is a vertex, each edge is an operation that leads to another vertex. So, obviously: Dijkstra works (or really just BFS, since the edges are unweighted), but not the fastest in the world. The fun one to play with would be A-star, but you'd have to find a suitable heuristic. One obvious candidate is that…

You could just run bfs from both starting and ending nodes until you find a node reachable from both the starting and ending nodes.

Re: Here's a puzzle game. I call it Reverse the List of Integers

#184

Post by 61u »

rokicki wrote: post #171

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)

Just wondering... How do you calculate the minimum number of steps fast enough?

Re: Here's a puzzle game. I call it Reverse the List of Integers

#185

Post by 61u »

61u wrote: post #183
OskarS wrote: post #146

Neat little problem! You could do SAT-solvers and stuff, but it's also obviously a graph search problem: each state is a vertex, each edge is an operation that leads to another vertex. So, obviously: Dijkstra works (or really just BFS, since the edges are unweighted), but not the fastest in the world. The fun one to play with would be A-star, but you'd have to find a suitable heuristic. One obvious candidate is that…

You could just run bfs from both starting and ending nodes until you find a node reachable from both the starting and ending nodes.

https://ideone.com/MGFwdo

I am running BFS from only the starting node because the graph is symmetrical.

Re: Here's a puzzle game. I call it Reverse the List of Integers

#186

Post by rokicki »

61u wrote: post #184
rokicki wrote: post #171

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)

Just wondering... How do you calculate the minimum number of steps fast enough?

To solve a particular position, I just use level-by-level breadth-first search until a level contains two values that are reverses of each other.

To explore the entire state space of possible initial positions, I use a number of tricks; I'll be writing that up pretty soon. I've explored through n=12 already, and expect to finish n=13 and n=14 pretty soon. I'm not sure if I'll be able to do n=15.

And by the way, I've found a position for n=14 that requires 206 moves to solve.

Re: Here's a puzzle game. I call it Reverse the List of Integers

#187

Post by davidalayachew »

GistNoesis wrote: post #169
two-star wrote: post #101

Hi. I'm the post's author. This was something I dashed off quickly, so I was a bit imprecise in the language. Clarifications: Only positive integers are meant to be allowed. (Zero excluded.) Combining is meant to work on adjacent pairs of integers. If this is used in coding interviews, I deny any responsibility. Unless it's used in interviewing me, in which case I will totally take credit.

I got nerd sniped :) and created https://github.com/unrealwill/ReverseListPuzzle to explore all the solutions, with graph algorithms.

Lol, they got me too. Mine has an algorithm to find a solution quickly, and another to find the shortest solution possible. I also created a very rudimentary GUI so that the game could be played. I'll clean the GUI up later though.

https://github.com/davidalayachew/ReverseTheListOfIntegers

Re: Here's a puzzle game. I call it Reverse the List of Integers

#188

Post by davidalayachew »

two-star wrote: post #101

Hi. I'm the post's author. This was something I dashed off quickly, so I was a bit imprecise in the language. Clarifications: Only positive integers are meant to be allowed. (Zero excluded.) Combining is meant to work on adjacent pairs of integers. If this is used in coding interviews, I deny any responsibility. Unless it's used in interviewing me, in which case I will totally take credit.

Thanks for posting this. I made a playable version of your game too. Bundled inside is algorithms for solving it as well.

https://github.com/davidalayachew/ReverseTheListOfIntegers

Post reply on HN