12 ms·
Here's a puzzle game. I call it Reverse the List of Integers
- self 2y agoStart 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.
- self 2y ago(not my post)
- orlp 2y agoIt's not possible in general, e.g. [3, 2, 1] can't be reversed.
- Karellen 2y ago[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.
- TylerE 2y agoThe article specified a list of positive integers, and you can’t go smaller than the smallest initial value.
- nishamarshalll 2y ago[flagged]
- stavros 2y agoWhere does it say that? It only says you can't go larger than the largest value.
- abetusk 2y agoThe constraints stated: * 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. You can make a negative number and you can go lower than the smallest but not greater than the largest, so you're wrong on both counts.
- j4cobgarby 2y agothe best I can find for [7, 5, 3] is: 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
- deleted 2y ago[deleted]
- probablypower 2y agoI came to the exact same solution. 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.
- deleted 2y ago[deleted]
- 317070 2y agoWhat I found: 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.
- HarHarVeryFunny 2y agoAnother 7-step version: 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
- thrdbndndn 2y agoThe 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 2y agoI think it's indirectly indicated by using the word "split".
- abecedarius 2y agoYes, 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.)
- selfie 2y agoCould a constraint solver just rip through this problem?
- polivier 2y agoThe number of variables is not constant in each step so modeling this would be trickier than usual. I feel like there is probably an more efficient DP approach for this though.
- gota 2y agodeosjr just posted a proposed Prolog solution in ~50 LOC https://news.ycombinator.com/item?id=40014035 https://news.ycombinator.com/item?id=40014035
- CamperBob2 2y agoIt was interesting to see GPT4 fail at it: https://chat.openai.com/share/02c12bbe-43cd-40da-b5df-33681db370d7 https://chat.openai.com/share/02c12bbe-43cd-40da-b5df-33681d... Not a bad benchmark problem. It didn't get very far, but maybe the next release will.
- lupire 2y agoChatGPT can't write programs or do logic to solve problems whole solutions aren't already in its input.
- CamperBob2 2y agoIt applied logical reasoning, just not quite enough of it. When it gets 10x better, which it will, it will be smarter than either of us. For those who don't find that prospect fascinating, other sites beckon.
- smtross 2y agoI encoded it in SMT (source code https://github.com/rdaly525/hnpuzzle https://github.com/rdaly525/hnpuzzle). Fun little challenge! Turns out there are 6 unique solutions for [7,5,3] in 6 steps
- thih9 2y agoThis 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 https://en.m.wikipedia.org/wiki/Tower_of_Hanoi
- seventytwo 2y agoWas 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.
- thaumasiotes 2y agoNo, not at all. In a Towers of Hanoi model, this is a completely trivial game. 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.
- GilbertErik 2y agoIn 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 https://en.wikipedia.org/wiki/Tower_of_Hanoi
- tczMUFlmoNk 2y agoThey'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.
- eschneider 2y agoA dynamic programming approach would work. Basically, try everything.
- CyberDildonics 2y agoWhat do you mean by that exactly and why would it be 'dynamic programming' ?
- Shorel 2y ago"Dynamic programming" is jargon from competitive programming. It sounds a lot more sophisticated than it is. In reality, it is nothing more than memoization of function calls into an array.
- CyberDildonics 2y agoMemoization is just caching so I'm not sure how that would make any difference here.
- jazpy 2y agoDifferent sets of moves can lead to the same state, so if you can cache that a given state will not lead to a solution you can stop exploring that branch when you encounter it again.
- CyberDildonics 2y agoIs that 'dynamic programming' or is that just keeping a set of explored states?
- 317070 2y ago> 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.
- sour-taste 2y agoI thought the game was cool so I built a little version of it here: https://blaise.gg/number_game/index.html https://blaise.gg/number_game/index.html
- Bewelge 2y agoThought the same, you beat me to it! Really like the tree-like view, might steal that idea later :-) https://bewelge.github.io/aNumberGame/ https://bewelge.github.io/aNumberGame/ (does not format well on mobile) Code: https://github.com/Bewelge/aNumberGame https://github.com/Bewelge/aNumberGame
- madcaptenor 2y agoI like that all possible moves are shown at once. Would it be possible to have the sequence be other than [7, 5, 3]?
- Bewelge 2y agoI added an url parameter so you can load it up with any sequence. Example for sequence 5,2,7 https://bewelge.github.io/aNumberGame?seq=5,2,7 https://bewelge.github.io/aNumberGame?seq=5,2,7
- madcaptenor 2y agoThanks!
- dangond 2y agoFun implementation! There's currently a bug that allows the same number to appear twice after a combination step (I was able to perform 2,3,7,5->5,7,5)
- madcaptenor 2y agoRan into this as well: I did [8, 1, 4] -> [5, 3, 1, 4] -> [5, 3, 5].
- jpablomr 2y agoComing soon to a coding interview near you!
- CoastalCoder 2y agoMy thoughts exactly. It would 100% fit in with the interviews I've had in the past year.
- mywittyname 2y agoGeez. I mean, I could do this, but probably not in a 45 minute interview without knowing how to solve the problem ahead of time.
- datascienced 2y agoleetcode hard++
- wruza 2y agoProbably solvable with hashmap then. Something make hash bucket-sum dependent and split/resize until it's done.
- HarHarVeryFunny 2y agoSeems 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.
- ericyd 2y agoI 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.
- anthk 2y ago.... (reverse 'list)
- deleted 2y ago[deleted]
- deleted 2y ago[deleted]
- commandlinefan 2y agoOh boy, give it three months and we're gonna start being asked this in coding interviews.
- deleted 2y ago[deleted]
- simonbarker87 2y agoI hate little puzzles like this when presented in isolation, my brain just bounces off them. 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!
- bluefirebrand 2y agoYeah, I agree 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
- simonbarker87 2y agoYep, the best solution to a puzzle is to just not do it as far as my brain is concerned!
- toppy 2y agoThe broader contexts could be this: look at this puzzle as a way for reinvent sorting as a delegation of operations (split + combine) instead of traditional "swapping" of values. As CPU arithmetic is faster then memory operations some real treasure may be hidden in this new approach.
- Thiez 2y agoThat is clearly nonsense, as the results of performing the arithmetic still need to be written back to memory, so it's just a swap with extra operations. See also the xor-swap.
- TillE 2y agoI agree, but I enjoyed doing Google's semi-secret random-invite-only "Foobar" challenge, which gives you a series of coding problems with a silly story attached. I think even that very minimal structure helps mentally elevate it from a boring math problem to a "real" scenario.
- paxys 2y agoI 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 2y agoSquinting 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.
- deosjr 2y agoHere's a gist in Prolog that I believe solves this puzzle: https://gist.github.com/deosjr/7314659509333ee2ad67dbf276e8d487 https://gist.github.com/deosjr/7314659509333ee2ad67dbf276e8d...
- jodrellblank 2y agoHere'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/ 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 https://www.youtube.com/watch?v=vdabv9EkYrY
- two-star 2y agoHi. 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.
- davidalayachew 2y agoThanks 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 https://github.com/davidalayachew/ReverseTheListOfIntegers
- sltkr 2y agoShould we assume the numbers are initially positive and distinct, too?
- Sebb767 2y agoThey must be, because otherwise you'd never be allowed to split or combine to create the final list.
- sltkr 2y agoGood point!
- keefle 2y agoTechnically there are cases in which you can. The repeated values will act like separators that you cannot act on (because once you act on one, as you said one cannot create the final list again), but then it becomes multiple instances of the puzzle which seems pointless
- dhartmei 2y agoBrute-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.
- amluto 2y agoAssuming negative numbers are not allowed, the how about: [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.
- bradser 2y agoMy 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 2y agowhat if we just interviewed people.
- golergka 2y agoWhy is this not an interview? I had very similar problems even on an interview to get in a math-oriented high school.
- nomel 2y agoIt'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.
- deleted 2y ago[deleted]
- jojojaf 2y agoSo like, infinity, infinity-1, infinity-2, etc.?
- glitchc 2y agoThe 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.
- OskarS 2y agoNeat 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 2y agoYou could just run bfs from both starting and ending nodes until you find a node reachable from both the starting and ending nodes.
- 61u 2y agohttps://ideone.com/MGFwdo https://ideone.com/MGFwdo I am running BFS from only the starting node because the graph is symmetrical.
- hnfong 2y agoHeuristic: Longest common subsequence of the current state vs the target?
- semi-extrinsic 2y agoI 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 https://editor.p5js.org/semi-extrinsic/sketches/IKOjwE7Vb
- rokicki 2y agoHere 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 2y agoJust wondering... How do you calculate the minimum number of steps fast enough?
- rokicki 2y agoTo 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.
- rokicki 2y agoFinished with a full state-space search of 11; worst case is indeed 106 (vs 126 for 10).
- rokicki 2y agoFinished 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.