Divide them all

2

A Math.SE user have a funny game explained as such:

  1. Pick a random positive integer X.

  2. Add +1, 0, -1 to make it divisible by 3Keep track of how much you've added and subtracted. That is your "score"..

  3. Divide by 3 to create a new X.

  4. Repeat steps 2 and 3 until you reach one.

I'm expecting the shortest code to give the correct score and the decomposition (as a list of the following values [+1;0;-1]) given an integer input.

Input => Expected score => Expected decomposition #explanation
12 => -1 => 0-1 #(12/3 => (4 - 1) / 3 = 1
                             ^^^
25 => 0 => -1+10  (25 - 1) / 3 => (8 + 1) / 3 => (3 + 0) / 3 => 1
                      ^^^            ^^^            ^^^

9320 => -1 => +1+1-10-1+1-1-1 #(9320 + 1) / 3 => (3107 + 1) / 3 => (1036 - 1) / 3 => (345 + 0) /3 => (115 - 1) / 3 => (38 + 1) / 3 => (13 - 1) / 3 => (4 - 1) / 3
                                     ^^^               ^^^               ^^^              ^^^             ^^^             ^^^             ^^^            ^^^

Thomas Ayoub

Posted 2018-05-28T14:19:37.217

Reputation: 287

Question was closed 2018-05-28T16:56:16.270

Related. (This challenge basically asks for the sum of digits of the balanced ternary representation.) – Martin Ender – 2018-05-28T14:25:30.273

1@MartinEnder it even sounds like a dup... I should enlarge my vocabulary in order to find them more easily. Thanks. – Thomas Ayoub – 2018-05-28T14:33:36.463

I personally don't think it's a dupe because the expected output isn't the bal-ternary representation so you still have to do a slightly different task. Very related though, I agree. – HyperNeutrino – 2018-05-28T14:46:26.330

Does our code have to include the "pick a random positive integer" part or can we take the number as input? – nimi – 2018-05-28T16:06:56.533

@nimi I think that "given an integer input" overrides what's said in the quote from Math.SE. – Arnauld – 2018-05-28T16:10:41.603

Suggested test cases: 121: [ -1, -1, -1, -1 ] --> -4, 122: [ 1, 1, 1, 1, 1 ] --> 5 – Arnauld – 2018-05-28T16:17:31.677

1@HyperNeutrino, asking for the decomposition and its sum is a pretty minor variant on asking for the decomposition. – Peter Taylor – 2018-05-28T16:57:00.807

@PeterTaylor I may be misinterpreting the challenge, but asking for the decomposition and asking for the digits seem like completely different tasks to me... – HyperNeutrino – 2018-05-28T17:48:35.803

1@Arnauld you're right about 12, and the fact that the ouptut code must give both score & decomposition. I'll make my next questions proof-read – Thomas Ayoub – 2018-05-28T18:55:38.523

@HyperNeutrino, isn't the decomposition just the digits? Actually, on trying it, it seems to be the digits (except the leading +1) reversed. That's possibly accumulating enough trivial modifications (skip the first digit, reverse, also output the sum) to add up to something non-trivial, but it's still borderline. – Peter Taylor – 2018-05-28T19:06:08.073

@PeterTaylor I personally think that finding the decomposition on its own is much more competitive than finding the digits and then doing that whole reversal procedure, but it is a very similar challenge and doesn't really add too much new to the existing challenge – HyperNeutrino – 2018-05-29T16:40:19.550

Answers

2

JavaScript (ES6), 46 bytes

Returns an array where:

  • the last term is the sum
  • all preceding terms are the decomposition
f=(n,s=0)=>n-1?[k=1-++n%3,...f(n/3|0,s+k)]:[s]

Try it online!

Arnauld

Posted 2018-05-28T14:19:37.217

Reputation: 111 334

Unless I'm misreading the spec/test cases, it doesn't look like you need to include the total in the output. – Shaggy – 2018-05-28T16:26:29.050

@Shaggy I don't really know for sure. I've asked the OP. – Arnauld – 2018-05-28T16:38:27.823

1

Python 3, 53 bytes

Credit to Mr.Xcoder

f=lambda i,*s:i>1and f(-~i//3,*s,1--~i%3)or[s,sum(s)]

Try it online!

Python 2, 55 bytes

f=lambda i,s=[]:i>1and f(-~i/3,s+[1--~i%3])or[s,sum(s)]

Try it online!

Python 2, 58 bytes

i,s=input(),[]
while~-i:s+=1--~i%3,;i=-~i/3
print s,sum(s)

Try it online!

Returns list with decomposition and sum of it

Dead Possum

Posted 2018-05-28T14:19:37.217

Reputation: 3 256

53 bytes in Python 3 using recursion. The Python 2 equivalent recursive function should be about 55 bytes long. Keeping this as a Python 2 full program, while~-i saves a byte. – Mr. Xcoder – 2018-05-28T16:42:54.777

@Mr.Xcoder Thanks! Don't you want to post Python 3 solution as separate answer? – Dead Possum – 2018-05-28T16:51:43.800

You're welcome! No, I'm good. Go ahead and use it however you want. – Mr. Xcoder – 2018-05-28T16:52:30.773

@Mr.Xcoder So there will be all solutions with credit to you :D – Dead Possum – 2018-05-28T16:56:47.020