6
\$\begingroup\$

The name of the challenge was prompted by this GIF and the GIF also gave me the idea.

Your challenge today is to take a input guaranteed to be \$2<=n<=100\$ and output a sequence of x and - characters.

The output for a number N represents a sequence of operations applied to 1 where x means "multiply by 2" and - means "subtract 1". Starting from 1, reading left to right and doing them in order will give you the number N that was inputted.

If you want, you can output using characters other than x and - so long as the choice is consistent through all outputs.

Your strings may be outputted in reverse so long as all are reversed or there is some indication of which are in reverse.

Your score is the source code's size in characters plus the total length of all outputs (again in characters). Have fun everyone!

\$\endgroup\$
1
  • 7
    \$\begingroup\$ If I'm not imagining things, I think we've had a similar challenge to produce a number by doubling and subtracting 1. Not sure how to search for it -- anyone remember it? I think most solutions took the binary expansion of n (or maybe n-1 or n+1) and read off the operations from there. This gave the shortest possible path, which surely would be the best strategy here too. \$\endgroup\$
    – xnor
    Jun 30 at 9:16

10 Answers 10

4
\$\begingroup\$

Python 2, 37 bytes (+830 char output = 867)

f=lambda n:2/n*"0"or`n%2*10`+f(-~n/2)

Try it online!

0 for double, 1 for decrement, in reversed order. -1 byte thanks to dingledooper for the base case.


Python 2, 39 bytes

lambda n:bin(n-1)[2:].replace('0','10')

Try it online!

1 for double, 0 for decrement

\$\endgroup\$
5
  • 1
    \$\begingroup\$ -2 bytes Try it online! \$\endgroup\$
    – Jakque
    Jun 30 at 10:24
  • \$\begingroup\$ @Jakque Thanks, but I'm gonna stick to Python 2 here. \$\endgroup\$
    – xnor
    Jun 30 at 10:24
  • \$\begingroup\$ 37 bytes \$\endgroup\$ Jun 30 at 10:27
  • \$\begingroup\$ @dingledooper Ah, nice, we don't have to handle n=1. \$\endgroup\$
    – xnor
    Jun 30 at 10:28
  • \$\begingroup\$ The second one (but not the first) also works in Python 3. \$\endgroup\$
    – dan04
    Jun 30 at 21:31
3
\$\begingroup\$

Python 2, 42 bytes, score = 872 (42 + 830)

f=lambda x:x>1and f(-~x/2)+"x"+x%2*"-"or""

Try it online!

This can be 43 bytes in python 3 by replacing /by //

\$\endgroup\$
1
  • \$\begingroup\$ Did an edit to retract my accidental downvote, sorry for the noise \$\endgroup\$
    – ovs
    Jun 30 at 17:48
3
\$\begingroup\$

Charcoal, 11 bytes, score 841

⭆↨⊖N²…x-⁻²ι

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

   N        Input number
  ⊖         Decrement
 ↨  ²       Convert to base 2
⭆           Map over digits and join
      x-    Literal string `x-`
     …      Truncated to length
         ²  Literal integer `2`
        ⁻   Subtract
          ι Current digit
            Implicitly print
\$\endgroup\$
1
  • \$\begingroup\$ What’s the score of this answer? \$\endgroup\$
    – Tim
    Jun 30 at 17:37
2
\$\begingroup\$

JavaScript (Node.js), 28 bytes + 830 chars in output = 858

f=n=>n^1?n%2*10+f(n+1>>1):''

Try it online!

"0" represents *2, "1" represents -1, Output is reversed.

Simple, but quite effective approach. Divides the number by two if it is even, else subtracts 1 from it.

Thanks to @A username for -3 bytes!

Thanks to @xnor for -2 bytes!

\$\endgroup\$
2
2
\$\begingroup\$

Vyxal, 6 bytes

‹bṅ0₀V

Try it Online! Xnor port. -2 thanks to Aaron Miller.

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

Python 3, 129 bytes, score = 129+830 = 959

def f(n,x=1):
 for y in range(2**x):
  c,s=1,''
  for i in' '*x:c+=~y%-2|c;s+='-x'[y%2];y//=2
  if c==n:return s
 return f(n,x+1)

Try it online!

Brute force all strings of all lengths starting from length 1.

thanks to ovs for -12 bytes

\$\endgroup\$
1
  • \$\begingroup\$ c,s=y&2**i and(c*2,s+'x')or(c-1,s+'-') can be shortened to c+=~y%-2|c;s+='-x'[y%2];y//=2. This doesn't need the i, so range(x) -> ' '*x saves a few more bytes. \$\endgroup\$
    – ovs
    Jun 30 at 9:55
1
\$\begingroup\$

Retina 0.8.2, 33 bytes, score 863

.+
$*
+`(1+)(\1(1)?)
$2x$#3$*-
1

Try it online! Link includes test cases. Try it online! Link is to test suite that counts the score. Explanation:

.+
$*

Convert to unary.

+`(1+)(\1(1)?)
$2x$#3$*-

Keep dividing by 2, rounding up, inserting an x each time but also a - if the result was rounded up, until the remainder is 1.

1

Delete the remaining 1.

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

Japt, 7 bytes, score: 837

Port of Neil's Charcoal solution, with a tweak and a bit of Japt trickery, so be sure to +1 them.

Uses 1 for x and 0 for -.

´¢Ë°ÍîA

Try it (footer converts output to xs and -s) or run all test cases

´¢Ë°ÍîA     :Implicit input of integer U
´           :Prefix decrement the U that's contained in the next shortcut
 ¢          :Convert U to binary string
  Ë         :Map
   °        :  Postfix increment to convert to an integer
    Í       :  Subtract from 2
     î      :  Repeat to that length
      A     :    10 (C-G (12-16), H (32), I (64) & L (100) would also work)
\$\endgroup\$
1
\$\begingroup\$

05AB1E, 6 bytes, score 836

<b0T.:

Port of most other answers.
Outputs 1 for x and 0 for -.

Try it online.

Would be 11 bytes if we'd use x- instead:

<b0T.:T„x-‡

Try it online.

Or alternatively:

<bε_>„x-s∍?

Try it online.

Explanation:

<            # Decrease the (implicit) input by 1
 b           # Convert it to a binary string
  0T.:       # Replace all "0"s with "10"s
             # (after which the result is output implicitly)

<b0T.:       # Same as above
      T„x-‡  # Transliterate "10" to "x-"
             # (after which the result is output implicitly)

<b           # Same as above
  ε          # For-each over each digit:
   _         #  Invert the bit (1 if 0; 0 if 1)
    >        #  Increase it by 1 (2 if 0; 1 if 1)
     „x-     #  Push string "x-"
        s    #  Swap so the earlier integer is at the top of the stack
         ∍   #  Shorten the "x-" string to this length
          ?  #  Pop and output it without trailing newline
\$\endgroup\$
0
\$\begingroup\$

A0A0, 186 bytes + 5841 output = 6027

P50P45
P50P50
P50P45
P45P50
P50P50
G-5I0A3V0G0P45S1A0
G-1A0A0
A0C3G1G1G1G1G1G1G1A0
A0L100S2M6
A0A1G-3G-3G-3G-3G-3G-3G-3A0
G-3
A0A0
G1G1A0C3G1G1A0
G-4G-4A0G-4G-4G-4A0
A1G-3G-3A0A1G-3G-3A0

We're making use of the fact that the challenge doesn't require us to give a shortest length sequence, just a sequence. For a language like A0A0, any math operation more fancy than multiplication already gets annoying to implement, so no complicated stuff here. Instead we generate a sequence by first going up to one hundred (with the sequence xxx-x-x-xx) and then just going down by one repeatedly until we hit the right number.

This penalizes us heavily in the output score, but it saves a lot of work in the actual code. (It does make for an even worse phone entry screen, though, so there's that.)

P50P45
P50P50
P50P45
P45P50
P50P50
G-5

This prints 222-2-2-22. I chose a different character than x (allowed per the challenge), since x has an ascii value of 120, which is three characters, whereas 2 is only two characters (ascii value 50). You could technically do unprintable ascii values to get into the single digits, but in my opinion that is a bit against the spirit of the question. This is split across two columns, which gives the same amount of bytes as a single column, but two columns makes it easier to read on this site.

I0 A3 V0 G0 P45 S1 A0
G-1 A0  A0
    A0  C3   G1  G1  G1  G1  G1  G1  G1  A0
    A0  L100 S2  M6
    A0  A1   G-3 G-3 G-3 G-3 G-3 G-3 G-3 A0
    G-3

We now need to loop. We first take the input, so we can generate the right amount of dashes for the sequence. We then put this in the operand and append this operand, as well as the rest of the instructions into the loop below. This completes a loop that loops starting from the input until the value one hundred and prints a dash every single time. These are the actual instructions in the loop.

L100 S2 M6 V0 G0 P45 S1
L100                    ; compare the operand to value one hundred, store result in operand
     S2                 ; add two to the operand
        M6              ; multiple the operand by six
           V0           ; the operand
              G0        ; goto the offset of the operand
                 P45    ; print a dash
                     S1 ; add one to the operand

The jumping always jumps to either the loop below it, or to nothing which halts the program. The loop below simply jumps back up to this loop.

A0  A0
G1  G1  A0  C3  G1  G1  A0
G-4 G-4 A0  G-4 G-4 G-4 A0
A1  G-3 G-3 A0  A1  G-3 G-3 A0

This is the loop that jumps back up to the first loop. It looks a bit weird, but that's because this loop doesn't do anything other than jump back up top, so we can manually evaluate the loop until it gets into a position that has the shortest amount of bytes. This configuration saves one byte from the next best configuration and thirteen bytes compared to the worst configuration.

Once the value is equal to one hundred (or greater, but that will never happen), the loop will jump down to a place beyond this loop which is empty and will thus halt the program.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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