-4
\$\begingroup\$

if you have a range of numbers with values missing, eg l=[1,2,9,10,99], you can always use modulus and subtraction to make all the numbers in the list cover a smaller range, for example: l%99%6=[1,2,3,4,0]. your task is to take in a list of numbers and output an equation which will map them to unique numbers in the range 0..len(list). a sample method for determining such an equation for any range is below, but there are likely easier ways to do this as it's just something I came up with right now.

the sample list will be l=[2,1,5,3,99,7,6]

  1. to get it into a format we can work with, sort the list and subtract the minimum value from each number:
    • sorted(l)-1=[0,1,2,4,5,6,98]
  2. to find the first break, subtract the index of each number:
    • tmp=[0,0,0,1,1,1,92]
  3. subtract the number which came after the break:
    • sorted(l)-1-4=[-4,-3,-2,0,1,2,94]
  4. mod your whole list by highest-lowest+1: (94)-(-4)+(1)
    • (sorted(l)-1-4)%99=[95,96,97,0,1,2,94]
repeat
  1. sorted((sorted(l)-1-4)%99)-0=[0,1,2,94,95,96,97]
  2. tmp=[0,0,0,90,91,92,93]
  3. sorted((sorted(l)-1-4)%99)-0-94=[-94,-93,-92,0,1,2,3]
  4. (sorted((sorted(l)-1-4)%99)-0-94)%98=[4,5,6,0,1,2,3]

now that we have a 0-6 range, we can output our equation: ((l-5)%99-94)%98 (which gives us [2,1,4,3,0,6,5] on the original input)

by the nature of the way this method works you'll never need to loop more than len(list) times, looping extra times will not affect the values in the list, and you can stop as soon as you get a tmp with all 0 values.

so shortest code in bytes wins. to be considered valid, a solution must be able to take input representing a unique, non-negative list of numbers and give back something representing an equation which will make the list of numbers have unique, non-negative values between 0 and one less than the length of the list.

you may assume that each value of the initial list will be unique, but you may not assume they will be in order, and they do not need to end up in the same order. (eg your equation may transform a list [8,0,2,3,5] to anything like [4,1,2,3,0] or [3,1,4,2,0] or [2,3,4,0,1] etc). you do not need to worry about parenthesis if you don't want to, you can just output a series of subtraction and modulus operations in order (just say in your answer what format your output takes).

\$\endgroup\$
6
  • 1
    \$\begingroup\$ Do we have to be optimal? \$\endgroup\$
    – Tbw
    Dec 26, 2023 at 19:10
  • \$\begingroup\$ Can we subtract negative or add? \$\endgroup\$
    – l4m2
    Dec 26, 2023 at 21:31
  • \$\begingroup\$ @Tbw as long as the equation you output makes the range hit every non-negative integer less than the length once, you're good. the equation can be as long as you want. (for example, the list in this question would have a more optimal equation with (l%91-5)%8 or l%95-1 which both also would be valid outputs for that range) \$\endgroup\$
    – guest4308
    Dec 26, 2023 at 23:52
  • \$\begingroup\$ @l4m2 yes, you can have addition, I would consider that the same operation as subtraction. (I will note that I don't think addition is useful to you though; that's why I specified subtraction in the question body) \$\endgroup\$
    – guest4308
    Dec 27, 2023 at 0:22
  • \$\begingroup\$ you're already giving us the algorithm... this is not code golf, this is code reduction \$\endgroup\$
    – Joao-3
    Jan 5 at 17:45

4 Answers 4

1
\$\begingroup\$

Charcoal, 53 bytes

≔lηWΦθ⁻…⌊θκθ«≔⊕⁻⌈θ⌊θζ≔⪫⟦(η-⌊ι)%ζ⟧ωη≧⁻⌊ιθ≧﹪ζθ»η¿⌊θ⁺-⌊θ

Try it online! Link is to verbose version of code. Explanation:

≔lη

Start with just the name of the list.

WΦθ⁻…⌊θκθ«

Repeat while there is a break in the list.

≔⊕⁻⌈θ⌊θζ

Calculate the span of the list.

≔⪫⟦(η-⌊ι)%ζ⟧ωη

Update the equation for the break and span.

≧⁻⌊ιθ≧﹪ζθ

Update the list for the break and span.

»η

Output the equation.

¿⌊θ⁺-⌊θ

Handle the case where there was no break in the list.

\$\endgroup\$
1
\$\begingroup\$

Jelly, 7 bytes

ṢṚ+J-;Ɱ

A monadic link which is called as a monad with a single argument, an unsorted list of non-negative integers, and returns a list structured as [[s1, m1], [s2, m2], …] where there are pairs of subtraction (- sn) and modulo (% mn) steps.

The test suite has three fixed examples followed by a randomly generated fourth example. It also proves that the supplied result works; the header encodes a dyadic link that takes the result as detailed above as its left argument and the original list of integers as the right; it returns the list of integers from 0..(len(n) - 1) that results from applying the specified transformations.

Explanation

Ṣ       | Sort
 Ṛ      | Reverse
  +J    | Add 1-indexed indices
    -;Ɱ | Prepend each with -1

Extends @l4m2’s observation that a series of plus ones can be used to simplify the task.

Original answer, Jelly, 25 bytes

’¹ƇŻÄạ
ṢI’k$§$żçɗṀ_Ṃ‘ƲṖṭṂ

A pair of links which is called as a monad with a single argument, an unsorted list of non-negative integers, and returns a list structured as [s0, [[s1, m1], [s2, m2]]] where s0 is an initial subtraction step and then there are zero or more pairs of subtraction (- sn) and modulo (% mn) steps.

The test suite has three fixed examples followed by a randomly generated fourth example. It also proves that the supplied result works; the header encodes a dyadic link that takes the result as detailed above as its left argument and the original list of integers as the right; it returns the list of integers from 0..(len(n) - 1) that results from applying the specified transformations.

Explanation

’¹ƇŻÄạ
ṢI’k$§$żçɗṀ_Ṃ‘ƲṖṭṂ­⁡​‎‎⁡⁠⁡‏⁠‎⁡⁠⁢‏⁠‎⁡⁠⁣‏⁠‎⁡⁠⁤‏⁠‎⁡⁠⁢⁡‏⁠‎⁡⁠⁢⁢‏‏​⁡⁠⁡‌⁢​‎‎⁡⁠⁡‏‏​⁡⁠⁡‌⁣​‎‎⁡⁠⁢‏⁠‎⁡⁠⁣‏‏​⁡⁠⁡‌⁤​‎‎⁡⁠⁤‏‏​⁡⁠⁡‌⁢⁡​‎‎⁡⁠⁢⁡‏‏​⁡⁠⁡‌⁢⁢​‎‎⁡⁠⁢⁢‏‏​⁡⁠⁡‌⁢⁣​‎‏​⁢⁠⁢‌⁢⁤​‎‎⁢⁠⁡‏⁠‎⁢⁠⁢‏⁠‎⁢⁠⁣‏⁠‎⁢⁠⁤‏⁠‎⁢⁠⁢⁡‏⁠‎⁢⁠⁢⁢‏⁠‎⁢⁠⁢⁣‏⁠‎⁢⁠⁢⁤‏⁠‎⁢⁠⁣⁡‏⁠‎⁢⁠⁣⁢‏⁠‎⁢⁠⁣⁣‏⁠‎⁢⁠⁣⁤‏⁠‎⁢⁠⁤⁡‏⁠‎⁢⁠⁤⁢‏⁠‎⁢⁠⁤⁣‏⁠‎⁢⁠⁤⁤‏⁠‎⁢⁠⁢⁡⁡‏⁠‎⁢⁠⁢⁡⁢‏‏​⁡⁠⁡‌⁣⁡​‎‎⁢⁠⁡‏‏​⁡⁠⁡‌⁣⁢​‎‎⁢⁠⁢‏‏​⁡⁠⁡‌⁣⁣​‎‎⁢⁠⁣⁢‏⁠‎⁢⁠⁣⁣‏⁠‎⁢⁠⁣⁤‏⁠‎⁢⁠⁤⁡‏⁠‎⁢⁠⁤⁢‏⁠‎⁢⁠⁤⁣‏‏​⁡⁠⁡‌⁣⁤​‎‎⁢⁠⁢⁣‏‏​⁡⁠⁡‌⁤⁡​‎‎⁢⁠⁣‏⁠‎⁢⁠⁤‏⁠‎⁢⁠⁢⁡‏‏​⁡⁠⁡‌⁤⁢​‎⁠‎⁢⁠⁢⁢‏‏​⁡⁠⁡‌⁤⁣​‎‎⁢⁠⁢⁤‏⁠‎⁢⁠⁣⁡‏⁠‎⁢⁠⁣⁢‏‏​⁡⁠⁡‌⁤⁤​‎‎⁢⁠⁤⁤‏‏​⁡⁠⁡‌⁢⁡⁡​‎‎⁢⁠⁢⁡⁡‏⁠‎⁢⁠⁢⁡⁢‏‏​⁡⁠⁡‌­

’¹ƇŻÄạ              # ‎⁡Helper link: takes a list of increments as its left argument and the range + 1 of the original list as its right and returns the modulos needed (with a redundant final one)
’                   # ‎⁢Subtract 1
 ¹Ƈ                 # ‎⁣Keep only those which are non-zero
   Ż                # ‎⁤Prepend a zero
    Ä               # ‎⁢⁡Cumulative sum
     ạ              # ‎⁢⁢Absolute difference (from the range + 1)
‎⁢⁣
ṢI’k$§$żçɗṀ_Ṃ‘ƲṖṭṂ  # ‎⁢⁤Main link
Ṣ                   # ‎⁣⁡Sort
 I                  # ‎⁣⁢Increments
         ɗṀ_Ṃ‘Ʋ     # ‎⁣⁣Following as a dyad, with the increments as the left argument and (max - min + 1) of the original list as the right
      $             # ‎⁣⁤- Following as a monad:
  ’k$               # ‎⁤⁡  - Split the list of increments after any which are >1
     §              # ‎⁤⁢  - Sum inner lists
       żçɗ          # ‎⁤⁣- Zip with the results of calling the helper link with the increments as the left argument and the range + 1 as the right
               Ṗ    # ‎⁤⁤Remove the last member of the list
                ṭṂ  # ‎⁢⁡⁡Tag onto the minimum of the original list
💎

Created with the help of Luminespire.

In brief, this works by separately constructing the right hand arguments needed for subtraction and the modulo separately. The arguments for subtraction are the increments, except where there are consecutive numbers (i.e. increments of 1), these are collapsed into the next non-consecutive one. The arguments for modulo start with the range + 1 and decrease each time by the non-consecutive gaps - 1.

\$\endgroup\$
1
\$\begingroup\$

Python 3.8 (pre-release), 56 bytes by Nick Kennedy

lambda x:[[-1,z+i]for(i,z)in enumerate(sorted(x)[::-1])]

Try it online!

Each pair to subtract then modulo

Python 3.8 (pre-release), 93 bytes

lambda x:['-',p:=min(x)]+g(sorted(x),p)
g=lambda x,p:x and['+',1,'%',x[-1]+1-p]+g(x[:-1],p-1)

Try it online!

That's why I need +

\$\endgroup\$
2
  • \$\begingroup\$ I see now. you could do the same with subtraction if you wanted to make exactly one value -1 and doing mod max+2, but I don't know if that's a shorter or longer program. \$\endgroup\$
    – guest4308
    Dec 27, 2023 at 1:03
  • 1
    \$\begingroup\$ tio.run/##LYxLCsMgFEXnruJNCkpfoLb0EyErsQ7SRKnQmGAMGDdvbZrR/… is shorter (if we permit a list of lists of the arguments for subtraction and modulo). If you want to add back in the operators that could be done for an extra eight bytes. \$\endgroup\$ Dec 27, 2023 at 18:03
0
\$\begingroup\$

Google Sheets, 87 bytes

=let(a,transpose(split(A1,",")),index(a-sort(mod(sequence(count(a)),count(a)),a,1)))

Put a string like 2,1,5,3,99,7 in cell A1 and the formula in cell B1.

something representing an equation which will make the list of numbers have unique, non-negative values between 0 and one less than the length of the list

The output is returned as a vertical array with values like 0,0,1,0,99,1,1. It is a list of numbers to subtract from each value in A1 in turn, using an equation like \$r\$\$i\$ = \$a\$\$i\$ - \$o\$\$i\$ where \$i\$ ∈ (0, length of list].

\$\endgroup\$
7
  • \$\begingroup\$ I think you misunderstood the question a bit. you're meant to output one equation which is applied to each number, not different values for each number. for example, if you put each number of the original list through %95-1, it gives a new, small, unique list, so %95-1 would be a good output. \$\endgroup\$
    – guest4308
    Dec 27, 2023 at 17:28
  • \$\begingroup\$ %95-1 applied to each of [2,1,5,3,99,7,6] makes [1,0,4,2,3,6,5] which is indeed 'unique numbers in the range 0..len(list)'. the point of the question is to output one(I suppose I used 'an' instead of 'one' but same meaning) equation that uses modulus and subtraction to golf the list down to the smallest range, and personally, I thought it was pretty clear that the one equation was meant to be applied to each item of the list, not a separate equation for each different item. do you have a suggestion for an edit which I could use to make this more clear? \$\endgroup\$
    – guest4308
    Dec 27, 2023 at 21:08
  • \$\begingroup\$ I have not edited the question at all, I am simply trying to figure out what you misunderstood. as I see it, this answers a question that is very different from what I have asked here, and I want to know why the words that I said have a different meaning from what I intended them to have. \$\endgroup\$
    – guest4308
    Dec 27, 2023 at 21:15
  • \$\begingroup\$ the question already says that the output consists of a 'series of subtraction and modulus operations in order'. I'm not 'adding criteria in the comments', I'm trying to figure out what criteria I even missed. to respond to your main question, would adding '...an equation of consecutive modulus and subtraction operators to be applied to each number of the list' rather than '...an equation' be more clear? \$\endgroup\$
    – guest4308
    Dec 27, 2023 at 21:25
  • \$\begingroup\$ also the answer to the meta post you linked specifically said that if you are unclear on the rules you should leave a comment asking like Tbw and l4m2 did rather than posting a protest answer... \$\endgroup\$
    – guest4308
    Dec 27, 2023 at 21:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.