5 ms·
It's not possible in general, e.g. [3, 2, 1] can't be reversed.
by orlp 3y ago
It's not possible in general, e.g. [3, 2, 1] can't be reversed.
- Karellen 3y 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 3y agoThe article specified a list of positive integers, and you can’t go smaller than the smallest initial value.
- nishamarshalll 3y ago[flagged]
- stavros 3y agoWhere does it say that? It only says you can't go larger than the largest value.
- abetusk 3y 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.
- tetris11 3y agoIt does feel implied albeit forgotten given the constrained nature of the task. Opening up the door to negative numbers feels like cheating.
- deleted 3y ago[deleted]
- Sharlin 3y agoHowever, 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 3y ago> 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.
- 3y ago
- simiones 3y agoThe 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 3y ago> 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.
- deleted 3y ago[deleted]
- thih9 3y agoTechnically 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 3y agoTechnically 1 is not smaller than 1 ;)
- roenxi 3y agoTo 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.
- tetha 3y agoHuh. 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 :)
- deleted 3y ago[deleted]
- deleted 3y ago[deleted]
- deleted 3y ago[deleted]
- thih9 3y agoTechnically 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 3y agoYeah, 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 3y agoNot 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.
- Etherlord87 3y agoYou'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 3y ago
- deleted 3y ago[deleted]
- HarHarVeryFunny 3y agoIt 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?
- GuB-42 2y agoAny 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.