Hi. I'm the post's author. This was something I dashed off quickly, so I was a bit imprecise in the language. Clarifications:<p>Only positive integers are meant to be allowed. (Zero excluded.)<p>Combining is meant to work on adjacent pairs of integers.<p>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 thought the game was cool so I built a little version of it here:<p><a href="https://blaise.gg/number_game/index.html" rel="nofollow">https://blaise.gg/number_game/index.html</a>
This can be transformed into a problem with pegs and moving blocks.<p>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.<p>Unless you want to deal with negative integers, then it would get more tricky.<p>[1]: <a href="https://en.m.wikipedia.org/wiki/Tower_of_Hanoi" rel="nofollow">https://en.m.wikipedia.org/wiki/Tower_of_Hanoi</a>
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.<p>The fun one to play with would be A-star, but you'd have to find a suitable heuristic. One obvious candidate is that if you have target list that is X long and a current list that is Y long, then you need at least abs(Y - X) steps to get there (since each step either adds or removes a number). That's admissable and would probably speed up the search quite a bit compared to regular BFS, but you could probably do a lot better. I'm thinking a heuristic based on the number of inversions or something.<p>I would suspect if you found a really good heuristic for A-star, that's about as good as you're going to get. Though maybe there's something more clever I'm not spotting.
Start with a list of positive integers, (e.g. [7, 5, 3]) and your goal is to make the same list, in reverse ([3, 5, 7]).<p>Operations:<p>1) Split an integer into two smaller integers. (e.g. [7, 5, 3] → [6, 1, 5, 3])
2) Combine (add) two integers into a larger one. (e.g. reverse the last e.g.)<p>Restrictions:<p>1) You can never make an integer greater than the largest integer in the original list.
2) You can never make a move that results in the same integer appearing in the list more than once.
The rules are too restrictive. Even a basic [1, 2] is not solvable.<p>For this game to be popular, the difficulty should grow (generally) with the size of the list and the relative differences between numbers.
Here's a gist in Prolog that I believe solves this puzzle:
<a href="https://gist.github.com/deosjr/7314659509333ee2ad67dbf276e8d487" rel="nofollow">https://gist.github.com/deosjr/7314659509333ee2ad67dbf276e8d...</a>
I made a completely graphical representation of this game in P5.js - it turned out quite intuitive I think.<p>The integers are represented by the number of edges in each straight section.<p><a href="https://editor.p5js.org/semi-extrinsic/sketches/IKOjwE7Vb" rel="nofollow">https://editor.p5js.org/semi-extrinsic/sketches/IKOjwE7Vb</a>
I like it, but it strikes me that there are actually not that many valid moves you can make in the example problem. Maybe this isn't true in other examples, but I found most of my time thinking about this was simply realizing that most of my desired moves were off limits. Perhaps that's the point, it just struck me.
Here are the maximum number of steps required through 10, and likely maximum number of steps required through 12:<p>6: 14
7: 26
8: 74
9: 86
10: 126
11: 106 (?) (full state space not explored)
12: 130 (?) (full state space not explored)
Squinting at this... Feels like there is some relationship to asking if you can tile a triangle into integer-length non isoceles triangles.<p>It feels like it is typically going to be impossible. Most puzzles will seem to have only a few legal moves at a time, all of which will either loop back to wehre they are or lead to victory.Generally speaking though,odd numbers are useful.
My first reaction to this was, "neat coding question for interviews". I started to try to solve it for a few seconds, then thought of when I've asked coding questions. Invariably starting by saying "The goal is to see how you approach and work through the problem, and less so whether you come up with the optimal solution". Then I thought, what if the interviewer and interviewee tackled the problem together, both coming in cold? And that was stated as such, up front? It would be much closer to the real world of tacking novel problems as a team. Taking the pressure of "I need to come up with the answer" off the interviewee should result in real focus on "working through the problem", and decrease interviewee stress; if the interviewer doesn't know the answer yet, how can they expect the interviewee to come up with one?<p>There are a couple of obvious downsides like:
What if it turns out the problem is too trivial? Move on to the next one.
What if the interviewee has already encountered the problem before? No different than if the interviewer posed an already-solved problem.<p>It would be incumbent upon the interviewer to not reveal a solution if they come up with it first of course. And the evaluation of "how you approach and work through the problem" is less definite than whether an answer (brute-force or optimal) was achieved; but if approach is indeed the important thing, that needs to be evaluated regardless. I'm sure there are other downsides I'm not seeing off the top of my head.<p>I can't be the first person to come up with this strategy, nor try it in real interviews. Has anybody attempted this? Was it successful or not, and why?<p>I can't tell if this strategy that just popped into my head is of value :-).
Seems like there are going to be non-search algorithmic solutions that solve these non-optimally, then god's solution where each split or combine works towards putting more than one number in place.
I hate little puzzles like this when presented in isolation, my brain just bounces off them.<p>If the EXACT same puzzle was presented as part of a real problem with context and reasons, my brain would be all over it and I'd work out a solution.<p>As another comment says, it will inevitably show up as a coding interview, one that I would likely fail!
Assuming negative numbers are not allowed, the how about:<p>[3, 2]<p>Creating a zero is useless, you can’t split 3 or 2, and you can’t make a 5.<p>[2, 1] is similarly stuck.