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

[two-star]

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.

[GistNoesis]

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

[dhartmei]

Brute-force says the hardest puzzle for n=6 is [1,6,3] with a minimum of 14 moves.

And for n=7 it's [5,4,1,2,7] with a minimum of 26 moves.

[davidalayachew]

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

[klyrs]

For whatever it's worth, zero gets you absolutely nowhere; there's no harm in allowing it.

[sltkr]

Should we assume the numbers are initially positive and distinct, too?

[sour-taste]

I thought the game was cool so I built a little version of it here:

https://blaise.gg/number_game/index.html

[b3orn]

Interesting, it appears I've encountered an impossible combination of numbers: [2, 5, 1, 3]

The only possible move is to add 1 and 3. Can't ever split a 2 as that would result in [1, 1], can't split the 5 because that would be [4, 1] or [3, 2], can't split the 3, as that would be [2, 1] or [1, 2], can't add the 5 to anything as that would be larger than 5.

[Bewelge]

Thought the same, you beat me to it! Really like the tree-like view, might steal that idea later :-)

https://bewelge.github.io/aNumberGame/ (does not format well on mobile)

Code: https://github.com/Bewelge/aNumberGame

[thih9]

This can be transformed into a problem with pegs and moving blocks.

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.

Unless you want to deal with negative integers, then it would get more tricky.

[1]: https://en.m.wikipedia.org/wiki/Tower_of_Hanoi

[Someone]

The charm of towers of Hanoi is that you can make a physical version where the legality of moves is easily verified because of the differently sized blocks.

I think the “you cannot have towers with the same amount of blocks” rule will make this a lot less charming, certainly if any of the numbers are larger than, say, 10.

There also is the issue of adding pegs, but that’s solvable by fixing the number of stacks (the triangular number for n is about ½n², so it certainly need not be larger than twice the square root of the number of blocks).

You can even make it smaller to get a variation on this game where the length of the list is limited.

[seventytwo]

Was just thinking this. There’s some differences, like the integers don’t have to be ordered biggest to smallest at any time, but it very much feels like Towers of Hanoi would be a good starting place to solve this.

[_nalply]

Yeah... Make a browser game out of it?

[orlp]

It's not possible in general, e.g. [3, 2, 1] can't be reversed.

[Karellen]

[3, 2, 1] has no valid modifications by the rules given.

I wonder how little wiggle-room there needs to be for a solution to be possible? Does [4, 2, 1] have a solution? You can get to with [4, -1, 3, 1] with one step, but I'm not sure where you can go from there.

[GuB-42]

Any combination where all consecutive numbers are present is unsolvable. That is [1..n], in any order.

That's because it is impossible to split any number, because it will create a duplicate, it is also impossible to merge, because it will either create a duplicate or a number >n

[2..n] (in any order) is also unsolvable for the same reason. And certainly many others ex:[1,2,4], finding if a problem is solvable is interesting in itself. A good solver should nor only find the shortest solution(s) if there is one but also determine if it is solvable. An interesting problem in itself.

[HarHarVeryFunny]

It seems that if the numbers are put in ascending order as min-max, then there would have to be at least two gaps in the sequence to make meaningful progress?

[thih9]

Technically the rules never state that when splitting an integer you have to put the new numbers in place of the old one, so...

[3, 2, 1]

[0, 2, 1, 3]

[2, 1, 3]

[0, 1, 2, 3]

[1, 2, 3]

I.e.: Split 3 into 3+0. Combine 0+2. Split 1 into 1+0. Combine 0+3 because rules don’t prohibit that either.

[OskarS]

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 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.

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.

[61u]

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

[hnfong]

Heuristic: Longest common subsequence of the current state vs the target?

[self]

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]).

Operations:

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.)

Restrictions:

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.

[Onavo]

Oh no, 2 dimensional dynamic programming? I have seen similar questions in competitive programming.

[jojojaf]

Can you only add adjacent integers?

[glitchc]

The rules are too restrictive. Even a basic [1, 2] is not solvable.

For this game to be popular, the difficulty should grow (generally) with the size of the list and the relative differences between numbers.

[deosjr]

Here's a gist in Prolog that I believe solves this puzzle: https://gist.github.com/deosjr/7314659509333ee2ad67dbf276e8d...

[jodrellblank]

Here's my Prolog code which solves (small inputs) of the puzzle, taking the core grammar of moves//3 from the Water Jug solution in Markus Triska's Power of Prolog video "Sparrows on Eagles: Delegate your work to Prolog!"[1] (I couldn't have written that style myself from scratch):

    :- use_module(library(dif)). % Sound inequality
    :- table split/2, merge/3, moves//3.
    
    % Replace one number H from a list with
    % two A and B which sum to that number.
    split([], []).
    split([H|T], [A,B|T]) :-
        between(1,H, A),
        between(1,H, B),
        dif(A,B),
        H is A+B.
    split([H|T], [H|T2]) :-
        split(T, T2).
    
    % Merge two adjacent numbers A and B from a list by
    % summing into H, unless that would exceed list Max.
    merge([], _, []).
    merge([H|T], Max, [H|T2]) :-
        merge(T, Max, T2).
    merge([A,B|T], Max, [H|T]) :-
        H is A + B,
        H =< Max.
    
    % Describes moves from starting state S0
    % to Target state, by splitting, merging,
    % and checking for duplicates using sort.
    moves(S0,   _, Target) --> { member(Target, S0) }.
    moves(S0, Max, Target) --> [Ns],
        { select(Ns0, S0, S),
          (split(Ns0, Ns)
          ; merge(Ns0, Max, Ns)),
          sort(Ns, NsSet), same_length(Ns, NsSet) },
        moves([Ns|S], Max, Target).
    
    
    solve(S0, [S0|Moves]) :-
        max_list(S0, Max),
        reverse(S0, Target),
        phrase(moves([S0], Max, Target), Moves).
        

e.g. with the query:

    ?- between(1, 20, MoveCount),
       length(Moves, MoveCount),
       solve([5,1,20], Moves).

Answer:

    Moves = [[7, 5, 3], [7, 1, 4, 3], [2, 5, 1, 4, 3], [2, 6, 4, 3], [2, 1, 5, 4, 3], [2, 1, 5, 7], [3, 5, 7]],
    MoveCount = 7

It will run in https://swish.swi-prolog.org/ clicking the 'Empty' then 'Program' and pasting the code in, querying (without the ?- and trailing .) in the lower right.

Taking the technique from the video; the query uses length/2 to lengthen the list of answer moves one at a time before the answer is sought, this code does iterative deepening and will find the shortest sequence of moves first.

[1] https://www.youtube.com/watch?v=vdabv9EkYrY

[commandlinefan]

Oh boy, give it three months and we're gonna start being asked this in coding interviews.

[thrdbndndn]

The rules for operation 2 didn't mention that two integers need to be next to each other (vise versa for operation 1). Is it a requirement?

[scotty79]

I think it's indirectly indicated by using the word "split".

[abecedarius]

Yes, this comes up in a reply further down the page. (Everyone, please upvote the parent comment to save other readers time. I was puzzled too.)

[semi-extrinsic]

I made a completely graphical representation of this game in P5.js - it turned out quite intuitive I think.

The integers are represented by the number of edges in each straight section.

https://editor.p5js.org/semi-extrinsic/sketches/IKOjwE7Vb

[ericyd]

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.

[rokicki]

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)

[61u]

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

[rokicki]

Finished with a full state-space search of 11; worst case is indeed 106 (vs 126 for 10).

[jpablomr]

Coming soon to a coding interview near you!

[paxys]

I feel like those last two rules would make the puzzle impossible to solve for most sets of inputs. E.g. in [3, 2, 1] all possible splits are illegal.

[spywaregorilla]

Squinting at this... Feels like there is some relationship to asking if you can tile a triangle into integer-length non isoceles triangles.

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.

[bradser]

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?

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.

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.

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?

I can't tell if this strategy that just popped into my head is of value :-).

[lawlessone]

what if we just interviewed people.

[nomel]

It's a problem because it's not deterministic. You need some kind of determinism when comparing 20 people a month and need to justify your position, especially if you're the only one saying no. The biggest problem is that are you, the interviewer, having a good day or a bad day? In your scenario, your performance is necessarily coupled in with the candidate, which is exactly what you don't want, for this goal of determinism.

I think a modification of this works well, and it's what I do:

1. Come up with a problem that's loosely contextually related to the work, and open ended. Leaving it open ended will test their communication and "problem navigation". The contextual relation allows you to, at the end of the interview, explain how it's contextual related to the work. This helps them understand their own performance, rather than leaving them feeling tricked with random puzzles.

2. If the problem is too out of context for the candidate's experience (which is often fine) provide a path that teaches them the background they would need. Makes this "training" path available and known to everyone. Make sure it doesn't take too much time. This helps the determinism since it doesn't rely on luck of some specific knowledge. Also, someone that communicates they want to go this path is the better candidate, regardless of experience, since information seeking is the best attribute of a colleague.

3. Explain that it's purposefully meant to be an open ended, so they should feel free to ask questions, and it's ok if they get stuck. This allows you to collaborate in a way that you can judge against others. Also, it reduces the adrenaline, which is important, because you can easily loose good candidates who "freeze up". Related, maintain positivity. If you seem annoyed, their performance can irrationally plummet. Personally, I'll do a second round if I see someone freeze up, especially if they haven't done many interviews, because I don't think interviewing for the skill of being interviewed is interesting, since I'm interviewing them to work with them.

4. With the above, the metric for their performance is all about communication, problem solving, and skill. The amount of explanation they needed to understand the fundamental problem, and how well they could fit it in their head, the amount of help they needed to implement it, the amount of mistakes they made, and how they reached out for help can be used to justify your yes or no, in a predictable way, that can be compared against others.

Across about 30 people, my observation of their actual performance, compared to my prediction from the interview performance, has been pretty darn close, with only a few outliers. The outliers were those that were either too familiar, or not at all familiar, with the problem space. The too familiar people appear to have better performance during the interview, since they're working from rote. The out of context people have the burden of not having the relationally-compressed version of the knowledge in their head, so run out of working memory. It's very easy, and somewhat fascinating, to see the moment when someone runs out. But, this is why the problem should be loosely related to the work: it's a valid criticism that "they're going to take significant time to ramp!".

I apologize for the wall, but this is something I'm interested in, and would love to see how others handle it. I think the Jim Keller way is the best, but it requires more than 45 minutes, and a certain level of seniority on the candidates side.

[HarHarVeryFunny]

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.