4
\$\begingroup\$

This prompt asked you to convert back and forth to factoradic, but is very limited in scope (only decimal integers from 0 to 10!-1). Your task in this challenge is to reach just a bit further and fully implement conversion between factoradic and any other integer base.

The factoradic system is extended to the reals by using reciprocals of factorials:

43210.001234 (max value at each position, ==DEC119.991666666... and ==DEC14399/120)
= 4      3      2      1      0   .  0        0        1        2        3        4
= 4*4! + 3*3! + 2*2! + 1*1! + 0*0! + 0*1/0! + 0*1/1! + 1*1/2! + 2*1/3! + 3*1/4! + 4*1/5!
= 96   + 18   + 4    + 1    + 0    + 0      + 0      + 1/2    + 1/3    + 1/8    + 1/30
= 119+119/120 (last two here lines are in decimal; but same idea for any other base)

Because of how this is defined, any real factoradic number has at most [denominator+1] digits past the decimal. As you can see from the above example, which has significantly less than 121 digits after the decimal, the number of digits required is much less for numbers with lots of factors. To convert in the other direction, a real numer a/b -> factoradic, requires a bit more effort. There may be an easier way to do this, but I couldn't find anyone who has done this before so I had to work out the formula myself. If you come up with an easier formula feel free to add it. Since we're working in multiple bases here, clarification may be needed: a number prefixed by a 3-letter abbreviation is being represented in the base which that prefix corresponds to, I am using the notation of baseN(#) to mean convert number # to base N, and unspecified numbers are in decimal for convenience.

14399/120 = 119 + 119/120

whole number portion:
119  / 4! = 4 r 23
23   / 3! = 3 r 5
5    / 2! = 2 r 1
1    / 1! = 1 r 0
0    / 0! = 0 r 0

fraction portion:
119/120 = 119/5!
base5(DEC119) = 434 (43 4)
base4(QUI43)  = 113 (11 3)
base3(QUA11)  = 12   (1 2)
base2(TRI1)   = 1    (0 1)
base1(BIN0)   = 0    (0 0)
base0(UNA0)   = 0    (0 0)

factorial:
43210.001234


bigger example:
123454321/11 = 11223120 + 1/11

whole number portion:
11223120 / 10! = 3 r 336720
336720   / 9!  = 0 r 336720
336720   / 8!  = 8 r 14160
14160    / 7!  = 2 r 4080
4080     / 6!  = 5 r 480
480      / 5!  = 4 r 0
0        / 4!  = 0 r 0
0        / 3!  = 0 r 0
0        / 2!  = 0 r 0
0        / 1!  = 0 r 0
0        / 0!  = 0 r 0

fraction portion:
1/11 = (1*(11-1)!)/11! = 3628800/11!

base11(DEC3628800) = 205940A (205940 A)
base10(ELE205940)  = 329890   (32989 0)
base9(DEC32989)    = 50224     (5022 4)
base8(NON5022)     = 7121       (712 1)
base7(OCT712)      = 1223       (122 3)
base6(SEP112)      = 145         (14 5)
base5(SEX14)       = 20           (2 0)
base4(QUI2)        = 2            (0 2)
base3(QUA0)        = 0            (0 0)
base2(TRI0)        = 0            (0 0)
base1(BIN0)        = 0            (0 0)
base0(UNA0)        = 0            (0 0)

factorial number:
30825400000.00002053140A

converting number n0 from base b1 to b2:
n0/b2 = n1 r d1     ( this only works )
n1/b2 = n2 r d2     ( if you actually )
n2/b2 = n3 r d3     ( do all the work )
..until n<b2...     ( in the 1st base )
n0 in b1 is n:...:d3:d2:d1 in b2, where
a colon represents separation of digits

if you can't do operations in other bases, first convert to base 10:
digit1 * b1^(#digits) + digit2 * b1^(#digits-1) + ... + digitn * b1^0 = number_in_base10

In words:
For the whole number part you take the floor of the number, and divide it by the largest factorial less than it, using the floor of that answer as the next digit and the remainder as the next argument.
For the fraction part, you multiply top and bottom until the denominator is a factorial n!, and convert the numerator to base n. Then remove the last digit and convert to the next lower base, using the full sequence of removed digits as the decimal.

You may notice that the three middle digits (...0.00...) are always 0. You may either include or exclude them, but state in your answer which you are going to do, and be consistent (ie, either your input and output both always use the abbreviated form like !1.1=DEC3/2 or they both always use the complete form like !10.001=DEC3/2).

Your code should take as input an input & output base, along with a real number represented in the input base, and then output that same real number in the output base. (depricated req) Note that at some point you will need to select a sub-base to represent the digits of numbers in bases larger than you can represent with one character. The higher you can get without falling back onto a sub-base the happier you will make me personally.

You may assume exactly one of either 'input' or 'output' must be in factoradic. Your output must take the same format as your input, ie your code should be able to back-convert anything it outputs. Numbers should be output in their simplest form (ie no leading/trailing 0's; no #/1's, 0/#'s, or #/0's; no -0; no #/-# or -#/-#; 6/4 -> 3/2; etc). (depricated req) In the spirit of flexible I/O you may use the default representation of higher-number bases for your language. Please state in your answer what format your numbers will use.

You may define the format for specifying 'input and output bases' in any way you like, as long as it can represent any integer base >= 2 and specifies whether the input will be going into or out of factoradic.
You may represent the non-factoradic number as either a/b (recommended) or as a real number n; if you use real number n as your input and output format you have to come up with a way to represent repeated digits like in DEC1/3, DEC1/7, or DEC1/28 (eg, digits after some delimiter repeat or something).
The factoradic part must be one number, you may not separately convert the numerator and denominator and return a fraction.

Examples:

radix: decimal-in
number: 14399/120
output: 43210.001234

radix: decimal-out
number: -43210.001234
output: -14399/120

radix: decimal-in
number: 123454321/11
output: 30825400000.00002053140A

radix: octal-in
number: -11656
output: -6543200

radix: hex-out
number: 42130100.001004
output: 4FD06/F

radix: 100-in
number(sub-base is hex): 1c|3|2f|62|35|5a|3/1|1e|4c|4a|24|50|0
output: 3110.0002223571381ccd

radix: binary-in
number: 0
output: 0

so shortest code in each language wins. You may assume input always follows your specified format, and it will always be a valid output as if your code had been given its own output and told to convert the other way. The logic of your code should work for any real number, converting between any positive integer base >=2 and factoradic in either direction. If your language has a built-in factoradic conversion function, you may include a secondary answer to show it off, but your first answer should not use it. Other integer base -> integer base conversion functions are fine.

\$\endgroup\$
7
  • 1
    \$\begingroup\$ Challenges here are normally flexible on I/O (without penalty) unless parsing/formatting is a key component of the challenge. Here it’s not the main task, and it’s already quite a complicated challenge without enforcing stricter I/O rules \$\endgroup\$ Commented Nov 27, 2023 at 8:18
  • 1
    \$\begingroup\$ The fourth answer seems to be missing a trailing zero on the factorial base result \$\endgroup\$ Commented Nov 27, 2023 at 12:04
  • 1
    \$\begingroup\$ @NickKennedy after staring at these two answers for a long time, I accept that I can't encourage using higher bases score-wise. still sad though ;; I was going to attempt something like ⌊log(N)*10⌋-10 for highest base N but it seems like that would take it out of code-golf \$\endgroup\$
    – guest4308
    Commented Nov 27, 2023 at 12:08
  • 1
    \$\begingroup\$ @NickKennedy aww, yup, you're right. it seems like every time I make examples I trust my sample code too much.... \$\endgroup\$
    – guest4308
    Commented Nov 27, 2023 at 12:09
  • 2
    \$\begingroup\$ In terms of other feedback, I think this might have worked better separated into two challenges (conversion to and conversion from factoradic), and potentially without the need to handle non-decimal bases on the non-factoradic side; in languages with a base conversion built-in, it just adds a few bytes, whereas in others it could add quite a few more. \$\endgroup\$ Commented Nov 28, 2023 at 8:24

1 Answer 1

1
\$\begingroup\$

Jelly, 94 93 bytes

⁹1!ḍ@¥1#ḢR;!:¥ɗU×1¦%Ḣd¥\FḊU
:1!>¥1#Ḣ’!€Ɗ;ƲUṪd¥\FḊ,ç
ḅç/
ẈḶ!U×¥:@ƭ€FṀ$©$ḋ⁸S;®:g/$b
A⁵ŀ⁹×1¦ṠFḢɗ

Try it online!

Test suite

A full program taking three arguments. The first argument is a list of two lists of integers. This will be base digits for the numerator and denominator if converting to the factoradic representation. If converting from factoradic representation, it will be the factoradic digits before and after the point. The second argument will be an integer representing the base and the third will be the integer 3 for conversion to factoradic representation and 4 for conversion from factoradic representation. The program prints a list of lists of integers representing the results of the conversion. When converting from factoradic, the result will always be a fraction in its simplest form, with a denominator of 1 for integers. When converting to factoradic, a zero whole number portion is represented as an empty list, while after the point there will always be the two fixed zeros (even if there are no other digits).

The TIO link runs a series of five variants of the test cases from the question, first converting to factoradic and then back again.

Integer maths is used throughout, so should handle any size of input.

Explanation

⁹1!ḍ@¥1#ḢR;!:¥ɗU×1¦%Ḣd¥\FḊU  # ‎⁡Helper link 1: takes numerator as left argument and denominator as right argument and returns the portion of the factoriadic representation after the point
⁹                            # ‎⁢Right argument (denominator)
 1!ḍ@¥1#Ḣ                    # ‎⁣Starting at 1, find the first integer where the factorial is divisible by the denominator (referred to as z below)
              ɗ              # ‎⁤Following as a dyad with the original denominator as the right argument
         R                   # ‎⁢⁡- Range (1 to z)
          ;  ¥               # ‎⁢⁢- Concatenated to:
           !:                # ‎⁢⁣  - The result
                             # ‎⁢⁣of dividing the factorial of z by the original denominator
               U             # ‎⁢⁤Reverse the order of the list
                ×1¦%         # ‎⁣⁡Multiply the first number (z!/denominator) by the result of numerator mod denominator
                    Ḣd¥\     # ‎⁣⁢Reduce by popping the head and then taking divmod the next member of the list, collecting up intermediate results
                        F    # ‎⁣⁣Flatten
                         Ḋ   # ‎⁣⁤Remove the original starting point for the reduction
                          U  # ‎⁤⁡Reverse the order of the list
‎⁤⁢
:1!>¥1#Ḣ’!€Ɗ;ƲUṪd¥\FḊ,ç      # ‎⁤⁣Helper link 2: takes numerator as left argument and denominator as right argument and returns the factoriadic representation
:                            # ‎⁤⁤Integer divide numerator by denominator
             Ʋ               # ‎⁢⁡⁡Following as a monad:
 1!>¥1#Ḣ                     # ‎⁢⁡⁢- Starting with one, find the first integer that has a factorial greater than this
           Ɗ                 # ‎⁢⁡⁣- Following as a monad:
        ’                    # ‎⁢⁡⁤  - Decrease by 1
         !€                  # ‎⁢⁢⁡  - Factorial of each integer from 1 to this
            ;                # ‎⁢⁢⁢- Concatenate to floor(numerator/denominator)
              U              # ‎⁢⁢⁣Reverse order of the list
               Ṫd¥\          # ‎⁢⁢⁤Reduce by popping the tail and then taking divmod the next member of the list, collecting up intermediate results
                   F         # ‎⁢⁣⁡Flatten
                    Ḋ        # ‎⁢⁣⁢Remove the original starting point for the reduction
                     ,ç      # ‎⁢⁣⁣Pair to the result of calling helper link 1 with the original arguments to this link
‎⁢⁣⁤
ḅç/                          # ‎⁢⁤⁡Helper link 3: takes the numerator
                             # ‎⁢⁤⁡and denominator as base digits as the left argument and a base as the right. Converts from that base, then calls helper link 2 with the numerator as the left argument and denominator as the right
‎⁢⁤⁢
ẈḶ!U×¥:@ƭ€FṀ$©$ḋ⁸S;®:g/$b   # ‎⁢⁤⁣Helper link 4: takes a factoradic representation as the left argument and a base as the right. Returns the base digits of the numerator and denominator after converting from factoradic
Ẉ                           # ‎⁢⁤⁤Lengths of list
 Ḷ                          # ‎⁣⁡⁡Range from
                            # ‎⁣⁡⁡0..each of these lengths -1
  !                         # ‎⁣⁡⁢Factorial (vectorised)
              $             # ‎⁣⁡⁣Following as a monad:
        ƭ€FṀ$©              # ‎⁣⁡⁤Use the following,  first chain for the first argument, second for the second, in both cases using the max of the flattened list as the right argument (and also preserving this max in the register)
   U×¥                      # ‎⁣⁢⁡- For the first argument, reverse the order and multiply by the max of the flattened list
      :@                    # ‎⁣⁢⁢- For the second, divide the max of the flattened list by this
               ḋ⁸           # ‎⁣⁢⁣Dot product with the original left argument
                 S          # ‎⁣⁣⁡Sum
                  ;®        # ‎⁣⁣⁢Append the register
                    :g/$    # ‎⁣⁣⁣Divide by the GCD of these (simplifying the fraction)
                        b   # ‎⁣⁣⁤Convert to the requested base
‎⁣⁤⁡
A⁵ŀ⁹×1¦ṠFḢɗ                  # ‎⁣⁤⁢Main link
A                            # ‎⁣⁤⁣Absolute
 ⁵ŀ⁹                         # ‎⁣⁤⁤Call the helper link indicated by argument 3
    ×1¦   ɗ                  # ‎⁤⁡⁡Multiply the first part of the result by:
       ṠFḢ                   # ‎⁤⁡⁢The first sign of the original first argument, flattened
💎

Created with the help of Luminespire.

\$\endgroup\$
2
  • \$\begingroup\$ does the footer not count towards the byte count in jelly? haven't seen other jelly answers use the footer, and I'm still crunching through the logic of the main program to understand what exactly it's doing, but removing or changing it deff effects the output. \$\endgroup\$
    – guest4308
    Commented Nov 27, 2023 at 19:05
  • 1
    \$\begingroup\$ @guest4308 The footer is just to handle the multiple test cases. I’ve posted a separate link with just a single case so you can play with it. The code is the same. \$\endgroup\$ Commented Nov 27, 2023 at 19:40

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.