Here's a puzzle game. I call it Reverse the List of Integers
mathstodon.xyz
mathstodon.xyz
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.
And for n=7 it's [5,4,1,2,7] with a minimum of 26 moves.
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.
It also violates Rule 1 because one of the splits is larger than the original number.
https://bewelge.github.io/aNumberGame/ (does not format well on mobile)
Example for sequence 5,2,7
Though I say the rule about repeated numbers is a bummer. I can see things might get easier (also it might be a more procedurally easy problem to solve) if this is allowed
Basically I don't think it's a "productive" complication
Like this:
https://blaise.gg/number_game/index.html?numbers=1%7E4%7E6%7...
[n, n-1]
[n-3, 3, n-1]
[n-3, 2, 1, n-1]
[n-3, 2, n]
[n-1, n]
[n, n-1]
[2, n-2, n-1]
[2, n-3, 1, n-1]
[2, n-3, n]
[n-1, n]
[3,4]
--> [1,2,4] --> 4 can't split because 2/2 and 3/1 are invalid
--> 4 can't initially split because 2/2 and 3/1 are both invalid
[5,6] --> [5,4,2] --> [5,1,3,2] --> [6,3,2] --> [6,5]
[7,8] --> [7,3,5] --> [7,1,2,5] --> [8,2,5] --> [8,7]
When you add more numbers, you need more wiggle room. So, [4,5,6] is problematic and probably [5,6,7].
[4,5,6]
--> [3,1,5,6] --> 6 can't break into 3, nor 5/1. It can do 4/2, but then 5 can't split. 5 also can't split.
--> [4,2,3,6] --> [4,2,3,1,5] --> [6,4,5] --> 4 can't split into 2/2. It can split to 3/1 but then 5 can't split
--> 6 can't initially split at all because 3/3, 4/2, and 5/1 are invalid
Even if [6,7,8] has a solution, I'm sure [6,7,8,9] does not.
6,7,8,9
6,3,4,8,9
6,3,4,8,2,7
9,4,8,2,7
9,4,8,2,1,6
9,4,3,5,2,1,6
9,7,5,2,1,6
9,7,5,3,6
9,7,8,6
9,5,2,8,6
9,5,2,1,7,6
9,5,3,7,6
9,8,7,6
6,7,8
6,7,5,3
6,7,1,4,3
6,8,4,3
6,8,7
6,3,5,7
6,2,1,5,7
8,1,5,7
8,6,7
8,4,2,1,6
8,4,3,6
8,7,6
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.
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.
The biggest issue with this game is that there's no guarantee that any arbitrary starting state has a valid solution. A much needed improved would be a simple rule for guaranteed reversible starting formations (if one even exists).
You’d also need a way to represent the order of the posts (the game is about a list of integers, not a set, so you can’t move from [4,5,6] to [10,5], for example)
I think a halfway decent visualization is one where you have n different cylinders of lengths 1 through n and a gutter of length of the sum of the numbers you start with (in the [4,5,6] example that would be 15). Next, place the cylinders for the starting position in the gutter in the order given, so that it completely fills it. Keep the others elsewhere.
Allowed moves then are:
- replace two cylinders that are side by side in the gutter by one of the sum of their lengths that you have available.
- replace a cylinder in the gutter by two available cylinders that together have the same length.
I think this way to visualize the game also might lead to a physical construction, but I don’t see on yet.
According to another comment, the best puzzle with a high number of 6 is [1,6,3] with a minimum of 14 moves.
This would mean you have 6 total rods, and two gutters. The puzzle gutter with a length of 10, and the storage gutter with a length of 11.
If you want more visual symmetry a high number of 7 allows you potentially 2 gutters of length 14.
Then, you can replace the linear gutter by a circular one and replace the cylinders by parts of a torus. That would make for a cooler look of the game (on the other hand: how would you easily see you’ve completed the puzzle?)
Unfortunately, you won’t be able to put the ‘spare’ parts in a concentric circle as that would have a different radius.
Hanoi isn't a good model for this, because the posts are not fixed in place and the units are all identical.
It's a bad physical game because the player has to do all the work to enforce the rules. The environment doesn't provide any useful assistance.
You'd reverse [7, 5, 3] by picking four discs off the first peg and putting them back down on the third peg.
The rules here only allow you to move stuff a single peg away from its origin.
[3,2,1][][]
=> [3,2][][1]
=> [3][][1,2]
=> [][][1,2,3]
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]:
+++++++ +++++ +++
+++(----) +++++ +++(++++)
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.
Read literally, the numbers are constrained to not jump over the 0. It might depend on interpretation (absolute value or distance from positive infinity?); but negatives are tricky to handle with these rules and I think they might be illegal.
I don't think that's pedantry. That's just a straightforward reading of the rules, and I missed the word "smaller", somehow. *shrug*
Well, it's easy to show that you can't go anywhere from there:
1. You can't combine the 1 with the 3, because you'd have two 4s.
2. You can't combine the -1 with the 4, because you'd have two 3s.
3. You can't (usefully) combine the -1 with the 3, because that just means you never took your previous move of splitting that pair out of the 2.
Those are all the possible applications of the combining rule. You can't apply the splitting rule either:
1. Splitting the four into positive integers will cause a duplicate.
2. Splitting a negative number out of the four will violate the rule against numbers larger than 4.
3. Splitting the 3 has the same problems. You can't take out a negative number without leaving a residual of 4 or more, and you can't take out a positive number without leaving a residual of 1.
4. Taking a -1, -2, or -3 out of the 1 will leave a duplicate, and taking a positive value out of the 1 is impossible.
5. You can split the -1 into [-3, 2]. But at that point you need to get rid of the 1 in final position so that you can combine the -3 into the 4, and there isn't a way to do that. Once you've gotten here, your list already contains every legal positive value.
E: Looking at the sibling comments, I'm disregarding negative numbers here. Probably that breaks the line of thought here.
For example, a sequence made up of all numbers from 1 to n is unsolvable. A sequence of [1, 2, ..., n-1, n+1] for n >= 3 also seems to be unsolvable, since no number up to n-1 can split into a smaller number (they are all in the list) and n+1 also cannot split, because 1 is in there.
So it seems that there would be an unsolvable class of lists along the lines of [1, 2, ..., k, ..., n-1, n+k] by that argument, because the n+k cannot split ever, because all numbers up to k are in that list.
And I guess for any unsolvable list with a max value of M, you can add any number below M into the unsolvable list, because that just removes moves.
Ah. Nerdsniped :)
Edit: disregard that, indeed the integers need to be smaller.
It also clearly shows right in the first example of the first rule that you can go smaller than the smallest initial value: [7, 5, 3] -> [6, 1, 5, 3] is the first legal move it shows, and you'll notice that 1 is smaller than 7, 5, or 3.
If you split 5 into 6 and -1... 6 ain't smaller than 5.
* You can never make an integer greater than the largest integer in the original list.
* You can never make a move that results in the same integer appearing in the list more than once.
So if the original list was [10, 1] and negative numbers were allowed, then [10, 2, -1] would be allowed.
1. Split an integer into two smaller integers.
2. Combine (add) two integers into a larger one.
Both suggest that negative numbers are not possible.
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.
[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.
3 is not smaller than 3, so you can't split 3 into 3+0.
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.
I am running BFS from only the starting node because the graph is symmetrical.
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.
For this game to be popular, the difficulty should grow (generally) with the size of the list and the relative differences between numbers.
:- 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).
?- between(1, 20, MoveCount),
length(Moves, MoveCount),
solve([5,1,20], Moves).
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
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.
The integers are represented by the number of edges in each straight section.
6: 14 7: 26 8: 74 9: 86 10: 126 11: 106 (?) (full state space not explored) 12: 130 (?) (full state space not explored)
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.
It would 100% fit in with the interviews I've had in the past year.
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.
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 :-).
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.
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.
As another comment says, it will inevitably show up as a coding interview, one that I would likely fail!
I think even that very minimal structure helps mentally elevate it from a boring math problem to a "real" scenario.
I tried doing leetcode for a while but basically just get bored of it
My brain is wired to solve problems and puzzles, but not in isolation. Removed of context I just can't convince myself there's any value in it and I bounce off just as you describe
[3, 2]
Creating a zero is useless, you can’t split 3 or 2, and you can’t make a 5.
[2, 1] is similarly stuck.
7 5 3
7 1 4 3
2 5 1 4 3
2 5 1 7
2 6 7
2 1 5 7
3 5 7
753 7512 762 7152 34152 3417 357
That's the same as your solution but in reverse.
It's not possible in 4 steps or less, because if you ignore the no-duplicates-rule, there is only 1 possibility and that one has duplicates. It's not possible in 5 steps, because you would not end up with an odd length list again. Solutions will always have an even number of steps. So six must be shortest.
My feel for this type of puzzle is that there is a 'gravity' from the higher to lower value integers. So you want to help integers flow from the 7 to the 3. The state of the list then represents a sieve that dynamically restricts the flow paths from one step to the next. So at any time step your possible paths to flow the integers from 7 to 3 are quite restricted.
The first step of 753 -> 7143 may seem arbitrary at first, but you quickly realise that most other options result in long awkward paths where you move integers back and forth, or deadends.
For example, if you decide to split the 7 first your valid moves are 753 -> 6153 or 753 -> 1653. The first move still leaves you overloaded at the left most position, and you still need another split because you cant combine 1+5 or 5+3 due to duplicates or exceeding 7. So you don't really feel closer. Same with 1653, putting you in a position where all combinations exceed 7, and you need to further breakdown numbers, but you've already used up all your valid odd numbers, so you have to break 6 into 2 and 4 -> 12453. This is a dead end.
Fun morning coffee puzzle.
753 7512 34512 3462 34152 3417 357
753 7512 762 7152 34152 3417 357
753 7512 762 3462 34152 3417 357
753 7143 25143 2643 21543 2157 357
753 7143 25143 2643 267 2157 357
753 7143 25143 2517 267 2157 357
Discovered using SAT/SMT
7 5 3
7 1 4 3
2 5 1 4 3
2 6 4 3
2 6 7
2 1 5 7
3 5 7
In reality, it is nothing more than memoization of function calls into an array.
No, it's the next step after memoization.
Recursion is the slowest approach of implementing many algorithms, as it will duplicate a lot of computation of subproblems. It solves a lot of subproblems many times.
Memoization is a cheap fix, it will not solve subproblems multiple times. It stores subproblems it has already solved, along with the solution. But it has an increasingly large state, keeping solutions of subproblems in memory which are actually no longer needed.
Dynamic programming is a manipulation on algorithms relying on memoization. It takes such an algorithm, and it makes the state as small as possible. So solutions of subproblems are discarded when they are no longer needed.
Like in memoization, dynamic programming will keep around previous subproblem solutions. But it will only keep the ones around it still needs in the future, and discard what is no longer needed. This often requires a change in representation of that state and in the order in which the subproblems are solved. But it will run much faster than recursion, on less memory than memoized approaches.
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'.
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.
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.
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?
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.
Actual "dynamic programming" would be self-modifying code, or something just as sophisticated, IMO. Or Prolog =)
What about "memoization optimized backtracking"?
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.
Turns out there are 6 unique solutions for [7,5,3] in 6 steps
Not a bad benchmark problem. It didn't get very far, but maybe the next release will.
For those who don't find that prospect fascinating, other sites beckon.