12
\$\begingroup\$

Write a program or function that takes in a positive integer N. Output a list of all the distinct decimal numbers that can be written in exactly N characters using digits (0123456789), decimal points (.), and negative signs (-).

For example, some numbers that would be in the N = 4 output list are 1337, 3.14, .999, -789, -2.7, and -.09.

The numbers are to be written in the normal way, but in as short a form as possible. This means:

  • The decimal point should only be included if the number is not an integer.

    • e.g. 45.0 and 45. should be written as plain 45
    • -45.00 should be written as -45
  • There should be no leading zeroes to the left of the decimal point.

    • 03 and 003 should be written as 3, but 30 and 300 are fine as they are
    • 0.3 and 00.3 should be written as just .3
    • -03 should be written as -3
    • -0.3 should be written as -.3
  • There should be no trailing zeroes to the right of the decimal point

    • .50 and .500 should be written as .5
    • 900.090 should be written as 900.09
  • The exception to the two last rules is zero itself, which should always be written as plain 0.

  • Positive signs (+) should not be used since they unnecessarily lengthen the number.

Also note that the negative sign (-) should not be used as a subtraction sign. It should only appear as the first character of numbers less than zero.

Formatting

The order of the output list of numbers does not matter. It could be ascending, descending, or completely mixed up. It only matters that all of the distinct numbers that can be written in N characters are present.

The list can be formatted in a reasonable way, using spaces, newlines, commas, or perhaps something else between the numbers, as long as things are consistent. Leading and trailing brackets (or similar) are alright but things like quotes around numbers are not. (i.e. don't visibly mix up strings and ints/floats in the output.)

For example, when N = 1, some valid outputs would be:

0 1 2 3 4 5 6 7 8 9
[1, 2, 3, 4, 5, 6, 7, 9, 0]
ans = { 5 8 9 1 3 2 0 3 4 7 6 }

But this would be invalid:

[0, 1, 2, 3, 4, "5", "6", "7", "8", "9"]

Examples

N = 1 -> 0 1 2 3 4 5 6 7 8 9

N = 2 -> -9 -8 -7 -6 -5 -4 -3 -2 -1 .1 .2 .3 .4 .5 .6 .7 .8 .9 10 11 12 ... 97 98 99

N = 3 -> -99 -98 ... -11 -10 -.9 -.8 ... -.2 -.1 .01 .02 ... .98 .99 1.1 1.2 ... 1.9 2.1 2.2 ... 2.9 3.1 ...... 9.9 100 101 ... 998 999

Lists are in ascending order, ellipsized in some places for reading convenience.

Scoring

The shortest code in bytes wins. In case of ties, the higher voted answer wins

\$\endgroup\$
  • \$\begingroup\$ Should -0 be valid output? \$\endgroup\$ – Doorknob Feb 5 '16 at 3:46
  • \$\begingroup\$ @Doorknob Also note that the negative sign (-) should not be used as a subtraction sign. It should only appear as the first character of numbers less than zero. \$\endgroup\$ – Mego Feb 5 '16 at 3:47
  • \$\begingroup\$ @Mego Yes. Is negative zero distinct from zero? \$\endgroup\$ – Doorknob Feb 5 '16 at 3:47
  • \$\begingroup\$ @Doorknob Is zero less than zero? \$\endgroup\$ – Mego Feb 5 '16 at 3:48
  • \$\begingroup\$ @Doorknob No. What Mego said, and also "[zero] should always be written as plain 0". \$\endgroup\$ – Calvin's Hobbies Feb 5 '16 at 3:48
2
\$\begingroup\$

Pyth, 47 45 bytes

Thanks to FryAmTheEggman for noting that the order does not matter.

jf!sm:Td)c".- \..*\. ^-?0. [.-]0*$"d^{`c_T17Q

Try it online.

The runtime is horrible, basically O(12n), but I tested it for n = 6 on my computer (which took 2 minutes). Running n ≥ 5 will time out online.

Due to the way I generate the characters 0123456789.- the output is in a really weird order.

One could technically remove the { near the end, but it would result in a complexity of O(19n). (It would also produce lots of duplicates, but that's allowed.)

Explanation

                  _T       -10
                 c  17     -10 / 17 = -0.5882352941176471
                `          representation: "-0.5882352941176471"
               {           uniquify: "-0.582394176"
              ^       Q    input'th Cartesian power
 f                         filter on:
         c"…"d               split this string by spaces
    m:Td)                    check if the parts match the current string
  !s                         true if none of the parts matched
j                            join by newlines

The main part of the code is ".- \..*\. ^-?0. [.-]0*$", which contains the regexes any output must not match.

.-         minus must be first character
\..*\.     there may only be one decimal point
^-?0.      no extra leading zeroes
[.-]0*$    number must not end with decimal/minus and 0+ zeroes
\$\endgroup\$
3
\$\begingroup\$

Pyth, 57 bytes

j-f:T"^0$|^-?([1-9]\d*)?(\.\d*[1-9])?$"0{.P*Q+jkUT".-"Q\-

Try it on the online interpreter.

Way too long, and with horrific runtime (takes several seconds for N=4, running with N=5 is not recommended).

            .P           Q    all permutations of length (input) of
                 jkUT         ... the string "0123456789"
                +    ".-"     ... plus the chars "." and "-"
              *Q              ... whole thing times the input -- pyth has
                              no repeated_permutation, so this is necessary
           {                  uniquify
  f                           filter by
   :T"..."0                   does it match the really long regex?
 -                        \-  get rid of "-"
j                             join on newline

Regex explanation:

^0$|            "0", or...
^
 -?             optional negative sign
 ([1-9]\d*)?    optional part-before-decimal
 (\.\d*[1-9])?  optional part-after-decimal
$
\$\endgroup\$
  • 1
    \$\begingroup\$ Not a golf, but I think you can put the *Q in your permutation making thing before the + so it only affects the digits, this should improve performance quite a bit. It might even help save some bytes in the regex? \$\endgroup\$ – FryAmTheEggman Feb 5 '16 at 4:55
2
\$\begingroup\$

Julia, 126 117 bytes

n->filter(i->ismatch(r"^0$|^-?([1-9]\d*)?(\.\d*[1-9])?$",i)&&i!="-",∪(map(join,combinations((".-"join(0:9))^n,n))))

This is a lambda function that accepts an integer and returns an array of strings. To call it, assign it to a variable. The approach here is the same as Doorknob's Pyth answer.

Ungolfed:

function g(n::Int)
    # Get all n-character combinations of .-0123456789
    c = combinations((".-"join(0:9))^n, n)

    # Join each group of n characters into a string and take unique
    u = ∪(map(join, c))

    # Filter to only appropriately formatted strings
    filter(i -> ismatch(r"^0$|^-?([1-9]\d*)?(\.\d*[1-9])?$", i) && i != "-", u)
end
\$\endgroup\$
1
\$\begingroup\$

MATL, 60 bytes

45:57iZ^!"@!'^(-?(([1-9]\d*)|([1-9]\d*)?(\.\d*[1-9]))|0)$'XX

Try it online!

This uses super-brute force (via Cartesian power) followed by filtering (via a regular expression). I'll add an explanation later.

The results are displayed at the end of the program. This may take a while. If you want to see results as they are generated, add D at the end:

45:57iZ^!"@!'^(-?(([1-9]\d*)|([1-9]\d*)?(\.\d*[1-9]))|0)$'XXD
\$\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.