161–170 of 188 posts
Earlier quoted context omitted.
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
Without that rule, you could decompose everything into 1's, and then recompose from there. Not the most efficient solution, but a boring one that always exists.
Earlier quoted context omitted.
I was given [1,2] in the second run. Even easier to see it's impossible.
Yeah the generation is very simple, 2-4 random numbers between 1 and 9 inclusive. Definitely gives impossible puzzles sometimes (because I don't know a general algorithm for generating possible ones only).
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…
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.
Earlier quoted context omitted.
I think it would be more fun if you only displayed problems that are solvable.
Yeah, I would but finding such puzzles is kind of hard. Might look into it this weekend
Earlier quoted context omitted.
Should we assume the numbers are initially positive and distinct, too?
They must be, because otherwise you'd never be allowed to split or combine to create the final list.
Earlier quoted context omitted.
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?
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.
Earlier quoted context omitted.
> 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 wi…
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.
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.
It's not possible in general, e.g. [3, 2, 1] can't be reversed.
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.