CODEWITHSUNDEEP
pythonalgorithmfunctionmath
Cortex0101
Cortex0101

Reputation: 927

Combining functions to produce a desired integer output

I'm not sure if this question belongs on stackoverflow or math, but I'll give stackoverflow a shot.

I'm attempting to create an algorithm / function that will allow me to solve a puzzle, but I am simply unable to. The puzzle is as stated.

  1. Let a unit be a function that accepts a integer i between 0 and 15.
  2. A unit can add or subtract any number in the range 0 - 15 to/from i.
  3. Additionally, instead of adding or subtracting a number to/from i, a unit can also contain a number from 0-15 and subtract i from that.
  4. A unit can only perform 2 operations on a number, and the operation producing the largest value will be the output of the unit.
  5. Values only go from 0 - 15, so 9 - 15 = 0 and 13 + 5 = 15.
  6. We may combine units together to produce a more complex result. The first unit may only accept numbers ranging from 0 - 9.
  7. In my examples I will string together 3 units.

This is a problem that is unrelated to coding, but it seems that I need a program to figure out possible solutions. I've attempted to create a brute force algorithm to find solutions, but I've been unable to do so, as I'm not that great with coding.

For example, a problem could be:

For values 1 and 4, let the output be 0. For all others, e.g. 0, 2, 3, 5, 6, 7, 8, 9, the output must be greater than 0.

A solution here might be:

def unit1(input):
    return max(5 - input, input)

def unit2(input):
    max(14 - input, input)

def unit3(input):
    max(10 - input, input - 10)

print(unit3(unit2(unit1(4))))

Another example might be:

For values 4, 5, 6 and 8 the output must be 3 or greater. For all others, e.g. 0, 1, 2, 3, 7, 9, the output must be less than 3.

A solution here might be:

def unit1(input):
    return max(4 - input, input - 4)

def unit2(input):
    max(2, input)

def unit3(input):
    max(1 - input, input - 6)

print(unit3(unit2(unit1(5))))

Given an example as the two stated above, is there a general algorithm / formula I can use to find my desired output?

Additionally, is it possible to solve the problems above using only 2 units?

Please do let me know if I need to elaborate on something, and know that your help is extremely appreciated!

Upvotes: 2

Views: 133

Answers (2)

Matt Timmermans
Matt Timmermans

Reputation: 59303

There seems to be basically two kinds of things you have to do: map inputs that should be handled the same way to contiguous ranges, and then move contiguous ranges to the right place.

max(A-x,x-B) is the only kind of unit that can map non-contiguous ranges together. It has limitations: It always maps 2 inputs onto one output, and you've gotta be careful never to map two inputs that have to be handled differently onto the same output.

In terms of what gets mapped together, you only need one parameter, since max(x,A-x) handles all cases. You can try all 16 possibilities to see if any of them help. Sometimes you may need to do a saturating add before the max to collapse inputs at the top or bottom of the range.

In your first example, you need to map 0 and 4 together.

In max(x,A-x), we need 4 = A-1.

Solving that we get A=5, so we start with

max(x, 5-x)

That maps 4 and 1 to 4, and everything else to other values.

Now we need to combine the ranges above and below 4. Everything less than 4 has to map to something higher than 4. We solve 5 = A-3 to get A = 8:

max(x, 8-x)

Now the ranges of things that need to be handled the same way are contiguous, so we just need to move them to the right place. We have values >=4 and we need 4->0. We could add a subtraction unit, but it's shorter just to shift the previous max by subtracting 4 from both cases. We're left with a final solution

max(x, 5-x)
max(x-4, 4-x)

You haven't really defined all the possible questions you might be asked, but it looks like they can all be solved by this two step combine-and-shift process. Sometimes there will be no solution because you can't combine ranges in any valid way with max.

Upvotes: 1

Karl Bielefeldt
Karl Bielefeldt

Reputation: 49118

I think your missing piece you need to proceed is a higher-order function. That's a function that returns another function. Something like:

def createUnit(sub, add):
    def unit(input):
        return max(sub - input, input + add)
    return unit

You can use it like:

unit1 = createUnit(5, 0)
unit2 = createUnit(14, 0)
unit3 = createUnit(10, -10)

Your first example can be solved with two units, but your second example can't.

I think the key to solving this efficiently is to work backwards from the output to the input, but I haven't spent enough time on it to figure out precisely how to do so.

Upvotes: 0

Related Questions