18
\$\begingroup\$

Challenge:

In the programming language of your choice, accept an integer as input in base 10, and output it in the negadecimal notation, which is also known as base -10

Example algorithm:

This is an algorithm taken from Wikipedia to convert base 10 to any negative base in VB.NET:

Function toNegativeBase(Number As Integer , base As Integer) As System.Collections.Generic.List(Of Integer)

    Dim digits As New System.Collections.Generic.List(Of Integer)
    while Number <> 0
        Dim remainder As Integer= Number Mod base
        Number = CInt(Number / base)

        if remainder < 0 then
            remainder += system.math.abs(base)
            Number+=1
        end if

        digits.Insert(0, remainder)
    end while

    return digits
end function

Obviously, you can use any algorithm, as long as it fulfills the challenge

Example inputs / outputs:

Input:

12

Output:

192

Another example:

Input:

2048

Output:

18168

Rule:

You must not use any built-in methods that solve this problem that exist in your programming language

This is a code-golf, so shortest code wins!

\$\endgroup\$
  • 3
    \$\begingroup\$ I think you only want to forbit built-ins that solve this specifiic problem and not all existing builltins. \$\endgroup\$ – Denker Jan 7 '17 at 15:08
  • \$\begingroup\$ Related OEIS: A039723 \$\endgroup\$ – devRicher Jan 7 '17 at 15:08
  • 6
    \$\begingroup\$ You should add a negative test case. \$\endgroup\$ – xnor Jan 7 '17 at 21:48
  • 1
    \$\begingroup\$ Would [0, 1, 8, 1, 6, 8] be an acceptable output for input 2048? \$\endgroup\$ – Dennis Jan 8 '17 at 2:20
  • 2
    \$\begingroup\$ That might be worth mentioning in the spec. Your VB code looks like it returns a list. \$\endgroup\$ – Dennis Jan 8 '17 at 23:46

12 Answers 12

12
\$\begingroup\$

JavaScript (ES6), 51 45 37 bytes

f=n=>n&&n%10+((k=n<0)+f(k-n/10|0))*10

Test cases

f=n=>n&&n%10+((k=n<0)+f(k-n/10|0))*10

console.log("12 -> " + f(12))
console.log("2048 -> " + f(2048))

\$\endgroup\$
  • \$\begingroup\$ Is there a reference for this algorithm? \$\endgroup\$ – dfernan Jan 7 '17 at 21:36
  • \$\begingroup\$ @dfernan I don't really know. This is the result of several golfing iterations, starting with the suggested algorithm. \$\endgroup\$ – Arnauld Jan 7 '17 at 22:47
5
\$\begingroup\$

Japt, 11 bytes

_ì ìAn)¥U}a

Test it online!

Explanation

_ì ìAn)¥U}a  // Implicit: U = input integer, A = 10
_        }a  // Return the smallest non-negative integer Z that returns a truthy value
             // when run through this function:
 ì           //   Convert Z to a list of its base 10 digits.
   ìAn)      //   Interpret this as a list of base -10 digits and convert to a base 10 integer.
       ¥U    //   Return (the result == U).
             // Implicit: output result of last expression
\$\endgroup\$
4
\$\begingroup\$

Batch, 82 bytes

@set/a"d=%1%%10,n=%1/-10-(a=d>>4),d-=a*10
@if %n% neq 0 %0 %n% %d%%2
@echo %d%%2

Batch's division truncates to zero, so if the remainder is negative I need to add 1 (and also add 10 to the remainder) to compensate. The digits are then accumulated in %2 until the result becomes zero.

\$\endgroup\$
4
\$\begingroup\$

Jelly, 9 bytes

Dḅ-10=ð1#

This is a brute-force inverse of negadecimal-to-integer conversion.

Try it online!

How it works

Dḅ-10=ð1#  Main link. Argument: n

      ð    Combine the links to the left into a chain and start a new, dyadic
           chain with left and right argument n.
       1#  Repeatedly execute the chain with left argument k = n, n + 1, ... and
           right argument n until the first match is found.
D          Convert k to decimal.
 ḅ-10      Convert the result from base -10 to integer.
     =     Compare the result with n.
\$\endgroup\$
3
\$\begingroup\$

Pyth - 9 bytes

Lel it has the crying emoji in it.

fqQijT;_;

Test Suite.

\$\endgroup\$
  • 1
    \$\begingroup\$ Why are you crying?? You are on par! \$\endgroup\$ – NoOneIsHere Jan 8 '17 at 6:52
  • \$\begingroup\$ Because he has the crying emoji on Pyth answer. \$\endgroup\$ – user75200 Dec 28 '17 at 15:38
3
\$\begingroup\$

Python 3, 35 bytes

f=lambda n:n and n%10+f(0-n//10)*10

Python port of Arnauld's algorithm.

Alternatively, for 102 bytes a generic function using the algorithm of the original post:

def f(n,b,r=0):
 if n:
  r,n=n%b,n//b
  if r<0:r+=abs(b);n+=1
  return f(n,b,r)+str(r)
 else:return ""
\$\endgroup\$
  • \$\begingroup\$ Python doesn't let you declare a default input that depends on another input. \$\endgroup\$ – xnor Jan 7 '17 at 21:46
  • \$\begingroup\$ @xnor It works on my Python installation: Python 3.5.1 (v3.5.1:37a07cee5969, Dec 5 2015, 21:12:44). \$\endgroup\$ – dfernan Jan 7 '17 at 21:49
  • \$\begingroup\$ How are you calling it? I'm doing this (in 3.5.2). Might you be declaring k or n elsewhere in the code? \$\endgroup\$ – xnor Jan 7 '17 at 21:53
  • 1
    \$\begingroup\$ Looks good, nice improvement! You don't need the parens around the function call any more. \$\endgroup\$ – xnor Jan 7 '17 at 22:16
  • 1
    \$\begingroup\$ The last one I can explain as operator precedence. -n//10 does -(n//10): negate n, then floor-divide by 10, which rounds down towards negative infinity, not 0. In contrast, 0-n//10 does 0-(n//10), which first floor-divides by 10, then negates. For whatever reason, Python treats unary negation with a higher precedence than binary minus. See this precedence table. I've run into this same situation before in golfing. \$\endgroup\$ – xnor Jan 7 '17 at 22:27
2
\$\begingroup\$

Jelly, 10 bytes

:⁵NµÐĿ%⁵ṚḌ

Try it online!

Background

Converting a list of non-negative from base b to integer can be achieved by left-folding by the function x, y ↦ bx + y. To convert and integer to base b, we must simply reverse that function, i.e., find an expression for bx + y ↦ x, y.

In Python (and, by extension, Jelly), the result of the modulo operator is always non-negative, so (bx + y) % |b| = y.

Also, integer division always rounds down, making sure that if q = n / d and r = n % d, the equality n = qd + r holds. If s is the sign of b, then (sx)|b| + y = bx + y, so sx = (bx + y) / |b| and, therefore, s((bx + y) / |b|) = x.

How it works

:⁵NµÐĿ%⁵ṚḌ  Main link. Argument: n

   µ        Combine the links to the left into a monadic chain.
    ÐĿ      Iteratively apply the chain until the results are no longer unique.
            Collect all unique results in an array.
:⁵            Divide the previous return value (initially n) by 10.
  N           Negate; multiply the result by -1.
      %⁵    Take all results modulo 10.
        Ṛ   Reverse the results.
         Ḍ  Convert from base 10 to integer.
\$\endgroup\$
2
\$\begingroup\$

SimpleTemplate, 147 bytes

This is a template language I've been working on.
By no means it is meant to be for golfing.
It even lacks complete basic math, but it allows to write tiny snippets of PHP directly.
This works around that issue.

{@setN argv.0}{@whileN}{@setM N}{@php$DATA[N]=($DATA[M]/-10)|0;$DATA[R]=$DATA[M]%-10}{@ifR is lower0}{@incby10 R}{@incN}{@/}{@setD R,D}{@/}{@echoD}

This throws a bunch of warnings.
The code is "compiled" into PHP.

Ungolfed, with trash whitespace:

{@set no argv.0}
{@while no}
    {@set temp_no no}
    {@php $DATA["no"] = ($DATA["temp_no"] / -10) | 0}
    {@php $DATA["remainder"] = $DATA["temp_no"] % 10}

    {@if remainder is lower than 0}
        {@inc by 10 remainder}
        {@inc no}
    {@/}
    {@set digits remainder, digits}
{@/}
{@echo digits}

If required, a set-by-step explanation can be added, but I believe that it is pretty straightforward.


Disclaimer:

The last commit, as of the time of writting this answer, was on 2017-01-07 20:36 UTC+00:00.
This works on commit 140e56ff38f45fa4fd40fd3ec382094e707b1bad from 2017-01-06 23:27 UTC+00:00.
That is the version used to run this answer.

The PHP code is available on https://raw.githubusercontent.com/ismael-miguel/SimpleTemplate/140e56ff38f45fa4fd40fd3ec382094e707b1bad/SimpleTemplate.php

I do recommend running this with the last version, but that one works fine for this question.


How to run?

Create a file with the code and run it like this:

<?php

    include 'path/to/SimpleTemplate.php';

    $template = new SimpleTemplate('<code>');

    $template->render(<number>);

The value will then be displayed on the screen.

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

PHP, 71 67 bytes

for(;$n=&$argn;$n=$g-$n/10|0)$d=($r=$n%10)+10*($g=$r<0).$d;echo+$d;

or 62 bytes for a port of Arnauld´s answer:

function n($n){return$n?$n%10+(($k=$n<0)+f($k-$n/10|0))*10:0;}
\$\endgroup\$
1
\$\begingroup\$

Mathematica, 49 bytes

d@0="";d@n_:=d[-Floor[n/10]]<>ToString[n~Mod~10];

Defines a function d taking one integer argument, and returning a string. A recursive algorithm—looks like the same algorithm in Arnauld's answer. It does work on negative numbers as well. (It returns the empty string intsead of "0" if the input is 0.) Note for Mathematica golfers: using ± requires one extra set of parentheses and thus seems not to be any shorter.

\$\endgroup\$
0
\$\begingroup\$

C, 68 bytes

main(f,a){f&&scanf("%d",&a);f=a?a%10+((f=a<0)+main(0,f-a/10))*10:0;}

Instead of printing the resulting number the program just returns it. Obviously this is Arnauld's answer, the only difference is that since C isn't an interpreted language I felt like I should make it a full program as opposed to just a function.

\$\endgroup\$
  • 1
    \$\begingroup\$ How is it returning it? f goes out of scope when the function returns unless I'm being really dumb. \$\endgroup\$ – abligh Jan 8 '17 at 19:14
  • \$\begingroup\$ @abligh You aren't being really dumb, it's just GCC being really dumb. If a non-void function terminates without a return it'll simply use the last assignment. \$\endgroup\$ – Etaoin Shrdlu Jan 9 '17 at 20:27
0
\$\begingroup\$

Rust, 88 bytes

fn g(mut n:i32)->i32{let mut r=n%10;n/=-10;if r<0{r+=10;n+=1;}if n==0{r}else{r+g(n)*10}}

This is just a recursive version of the algorithm provided in the question.

\$\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.