[HN Gopher] Here's a puzzle game. I call it Reverse the List of ...
___________________________________________________________________
Here's a puzzle game. I call it Reverse the List of Integers
Author : self
Score : 145 points
Date : 2024-04-12 06:59 UTC (16 hours ago)
(HTM) web link (mathstodon.xyz)
(TXT) w3m dump (mathstodon.xyz)
| self wrote:
| 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 wrote:
| Oh no, 2 dimensional dynamic programming? I have seen similar
| questions in competitive programming.
| jojojaf wrote:
| Can you only add adjacent integers?
| self wrote:
| (not my post)
| saagarjha wrote:
| If you hadn't mentioned it I would have thought this was a
| self-post...
| yccs27 wrote:
| So it's a self post, but not a self-post. Sorry, I'll see my-
| self out.
| orlp wrote:
| It's not possible in general, e.g. [3, 2, 1] can't be reversed.
| Karellen wrote:
| [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 wrote:
| The article specified a list of positive integers, and you
| can't go smaller than the smallest initial value.
| stavros wrote:
| Where does it say that? It only says you can't go larger
| than the largest value.
| TylerE wrote:
| The rule states " 1. Split an integer into two smaller
| integers."
|
| If you split 5 into 6 and -1... 6 ain't smaller than 5.
| stavros wrote:
| You said "you can't go smaller than the smallest initial
| value". If I have [5, 3] I can do [4, 1, 3], which you
| assert I can't.
| abetusk wrote:
| The 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.
| tetris11 wrote:
| It does feel implied albeit forgotten given the
| constrained nature of the task. Opening up the door to
| negative numbers feels like cheating.
| Sharlin wrote:
| However, as a result of #1, you in fact _cannot_ make
| negative integers. It's not possible to split a
| nonnegative integer into two lesser-or-equal integers
| such that either of them is negative.
| DougBTX wrote:
| > largest integer in the original list
|
| So if the original list was [10, 1] and negative numbers
| were allowed, then [10, 2, -1] would be allowed.
| Sharlin wrote:
| Oops, indeed!
| wvalurejr wrote:
| I believe Sharlin is correct here. Rule #1 states `Split
| an integer into two smaller integers.` 1 -> [2, -1]
| breaks this rule due to 2 not being smaller than 1.
| adbachman wrote:
| the only moves available are:
|
| 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.
| simiones wrote:
| The article says you _start_ with a list of positive
| integers.
|
| 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.
| thaumasiotes wrote:
| > You can get to with [4, -1, 3, 1] with one step, but I'm
| not sure where you can go from there.
|
| 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.
| thih9 wrote:
| Technically there are valid modifications, you can modify
| [3,2,1] into [3,2,0,1]; but yes, this doesn't change much.
|
| Edit: disregard that, indeed the integers need to be smaller.
| FL1ppY wrote:
| Technically 1 is not smaller than 1 ;)
| roenxi wrote:
| To be pedantic, this isn't the operation he gave - "split an
| integer into 2 smaller integers" is the operation, but 2 into
| [3, -1] is splitting it into a larger and smaller integer.
|
| 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.
| Karellen wrote:
| > To be pedantic,
|
| I don't think that's pedantry. That's just a
| straightforward reading of the rules, and I missed the word
| "smaller", somehow. *shrug*
| sltkr wrote:
| Are you being pedantic about pedantry?
| tetha wrote:
| Huh. There's bound to be some weird constraint there.
|
| 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 :)
| thih9 wrote:
| 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.
| Sharlin wrote:
| Yeah, the problem is slightly underspecified, though it's
| pretty obvious that you're not allowed to do swaps as that
| obviously makes the problem trivial.
| thih9 wrote:
| Not trivial - I do not see how to solve [3, 2, 1] without
| this kind of swapping. Perhaps we need to clarify the rules
| for a starting point first.
| Sharlin wrote:
| I mean that if you allow swapping then every instance of
| the problem becomes trivial because swapping is all that
| reversing is. Doesn't mean the problem as intended is
| always solvable.
| anthk wrote:
| Learn Forth. Consequent swappings will reverse an stack.
| Etherlord87 wrote:
| You're supposed to split an integer into two *smaller*
| integers.
|
| 3 is not smaller than 3, so you can't split 3 into 3+0.
| thih9 wrote:
| Oh, good spot. Yeah, no luck then.
| HarHarVeryFunny wrote:
| 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?
| j4cobgarby wrote:
| the 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
| 317070 wrote:
| What 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.
| probablypower wrote:
| I 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.
| HarHarVeryFunny wrote:
| Another 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
| smtross wrote:
| The following should be all the smallest solutions for [7, 5,
| 3]:
|
| 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
| thrdbndndn wrote:
| 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 wrote:
| I think it's indirectly indicated by using the word "split".
| lupire wrote:
| When I split an atom, The pieces go pretty far apart
| abecedarius wrote:
| 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.)
| selfie wrote:
| Could a constraint solver just rip through this problem?
| polivier wrote:
| The 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 wrote:
| deosjr just posted a proposed Prolog solution in ~50 LOC
|
| https://news.ycombinator.com/item?id=40014035
| CamperBob2 wrote:
| It was interesting to see GPT4 fail at it:
| 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 wrote:
| ChatGPT can't write programs or do logic to solve problems
| whole solutions aren't already in its input.
| CamperBob2 wrote:
| It 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 wrote:
| I encoded it in SMT (source code
| https://github.com/rdaly525/hnpuzzle). Fun little challenge!
|
| Turns out there are 6 unique solutions for [7,5,3] in 6 steps
| thih9 wrote:
| 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
| seventytwo wrote:
| 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.
| thaumasiotes wrote:
| No, 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 wrote:
| In 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
| tczMUFlmoNk wrote:
| They'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.
| _nalply wrote:
| Yeah... Make a browser game out of it?
| Someone wrote:
| 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 1/2n2, 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.
| dwallin wrote:
| You can make a physical version by having one fixed height
| pole for each integer up to the max, and then an equal number
| of post holes. Eg. If you wanted to support a game up to the
| integer 10 you would need 10 posts with lengths from 1 to 10
| units, and 10 post holes.
|
| 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).
| lupire wrote:
| Post holes are useless, because you can split left and then
| split back to the right. So all you need are the n tokens.
|
| 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.
| Someone wrote:
| > If you wanted to support a game up to the integer 10 you
| would need 10 posts with lengths from 1 to 10 units, and 10
| post holes.
|
| 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.
| dwallin wrote:
| I really like this. I could see constructing a physical
| artifact for a specific case of this game.
|
| 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.
| Someone wrote:
| Thinking it through a bit more, I would consider a
| variation on this game, where you don't have a list but a
| ring buffer.
|
| 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.
| eschneider wrote:
| A dynamic programming approach would work. Basically, try
| everything.
| CyberDildonics wrote:
| What do you mean by that exactly and why would it be 'dynamic
| programming' ?
| Shorel wrote:
| "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 wrote:
| Memoization is just caching so I'm not sure how that would
| make any difference here.
| jazpy wrote:
| Different 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 wrote:
| Is that 'dynamic programming' or is that just keeping a
| set of explored states?
| 317070 wrote:
| > 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.
| CyberDildonics wrote:
| Keeping the intermediate results of computations is just
| called programming. They go into a variable or a data
| structure like a vector or a hash map.
| ch33zer wrote:
| I thought the game was cool so I built a little version of it
| here:
|
| https://blaise.gg/number_game/index.html
| Bewelge wrote:
| 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
| madcaptenor wrote:
| I like that all possible moves are shown at once. Would it be
| possible to have the sequence be other than [7, 5, 3]?
| Bewelge wrote:
| I 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
| madcaptenor wrote:
| Thanks!
| dangond wrote:
| Fun 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 wrote:
| Ran into this as well: I did [8, 1, 4] -> [5, 3, 1, 4] -> [5,
| 3, 5].
| glenjamin wrote:
| This is neat, but your implementation does seem to allow
| duplicates sometimes
| minikomi wrote:
| Jumping in with my janky version: http://poyo.co/list-of-
| integers/
| fragmede wrote:
| I really like the visual aspect of your implementation
| b3orn wrote:
| 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.
| kleiba wrote:
| Couldn't you split 3 into [4,-1] ?
| b3orn wrote:
| None of the implementations support negative numbers, but
| the rules say integer which includes negative numbers, so
| that should be a legal move.
| Tao3300 wrote:
| Negative numbers would break the game by making the
| number of possible splits infinite. E.g. 1 could split
| into [-2, 3], [-3, 4], [-4, 5], etc.
|
| It also violates Rule 1 because one of the splits is
| larger than the original number.
| basil-rash wrote:
| Rules say you can't ever produce a number greater than
| the original largest number, so the possibilities will
| always be finite. (fixed number of ways to make a list of
| distinct integers that sum to N such that all values are
| <=M).
| fuglede_ wrote:
| They also say that a given integer should be split into
| two smaller integers.
| plg94 wrote:
| I was given [1,2] in the second run. Even easier to see it's
| impossible.
| spywaregorilla wrote:
| Gave me [2,1] which is not possible
| jxding wrote:
| It does seem like [n,n+1] is always unsolvable!
| ahahahahah wrote:
| [9,8] -> [6,3,8] -> [6,2,1,8] -> [6,2,9] -> [8,9]
| klyrs wrote:
| Indeed, [n, n-1] [n-3, 3, n-1]
| [n-3, 2, 1, n-1] [n-3, 2, n] [n-1, n]
|
| Works for all n greater than... 6?
| klyrs wrote:
| Optimizing self-response! That fails for six because n-3
| and 3 co-occur. With a slight modification we can make it
| work for all n>5 [n, n-1] [2, n-2,
| n-1] [2, n-3, 1, n-1] [2, n-3, n] [n-1,
| n]
|
| edit: and it's not hard to show that n<6 are impossible,
| so the solution above is optimal in that sense.
| adotbacon wrote:
| Yeah, the [n,n+1] is only a problem when there isn't
| enough wiggle room between the numbers. ex: [2,3] and
| [3,4]
|
| [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.
| madcaptenor wrote:
| A solution for [6,7,8,9]:
|
| 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
| adotbacon wrote:
| Wow, well done! I found [6,7,8] as well:
|
| 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
| mywittyname wrote:
| Would be nice if you allowed users to define their own puzzle.
| I had to set a break point at the right location and call
| startNew([..my array]) to do so.
| IshKebab wrote:
| Nice. It does let me make the same integer twice though.
| joelthelion wrote:
| I think it would be more fun if you only displayed problems
| that are solvable.
| raverbashing wrote:
| Cool!
|
| 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
| jpablomr wrote:
| Coming soon to a coding interview near you!
| CoastalCoder wrote:
| My thoughts exactly.
|
| It would 100% fit in with the interviews I've had in the past
| year.
| mywittyname wrote:
| Geez. 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 wrote:
| leetcode hard++
| wruza wrote:
| Probably solvable with hashmap then. Something make hash
| bucket-sum dependent and split/resize until it's done.
| HarHarVeryFunny wrote:
| 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.
| ericyd wrote:
| 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.
| anthk wrote:
| .... (reverse 'list)
| commandlinefan wrote:
| Oh boy, give it three months and we're gonna start being asked
| this in coding interviews.
| simonbarker87 wrote:
| I 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 wrote:
| Yeah, 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 wrote:
| Yep, the best solution to a puzzle is to just not do it as
| far as my brain is concerned!
| toppy wrote:
| The 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 wrote:
| That 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 wrote:
| I 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.
| norir wrote:
| I came here to post that I think this game is an evil ddos
| attack.
| paxys wrote:
| 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 wrote:
| 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.
| deosjr wrote:
| Here's a gist in Prolog that I believe solves this puzzle:
| https://gist.github.com/deosjr/7314659509333ee2ad67dbf276e8d...
| two-star wrote:
| 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.
| sltkr wrote:
| Should we assume the numbers are initially positive and
| distinct, too?
| Sebb767 wrote:
| They must be, because otherwise you'd never be allowed to
| split or combine to create the final list.
| sltkr wrote:
| Good point!
| dhartmei wrote:
| 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.
| amluto wrote:
| Assuming 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 wrote:
| 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 wrote:
| what if we just interviewed people.
| nomel wrote:
| 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.
| jojojaf wrote:
| So like, infinity, infinity-1, infinity-2, etc.?
| glitchc wrote:
| 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.
| OskarS wrote:
| 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.
___________________________________________________________________
(page generated 2024-04-12 23:01 UTC)