8
\$\begingroup\$

This challenge is based on the idea of Plouffle's Inverter.

Write a program in any language that does the following:

  • Takes as input a non-negative rational number X written in decimal, for example 34.147425.

  • Returns a mathematical expression using only non-negative integers, whitespace, parentheses, and the following binary operators:

    • Addition +
    • Subtraction -
    • Multiplication *
    • Division /
    • Exponentiation ^

    The expression should evaluate to X, or at least agree with all the digits of X. To continue the example, a correct output could be 13 + 20^(5/4) / 2, since 13 + 20^(5/4) / 2 = 34.1474252688...

  • Output may optionally be written in Polish notation (prefix) or reverse Polish notation (postfix), i.e. + 13 / ^ 20 / 5 4 2 is fine.

The program is subject to the following retrictions:

  • Standard loopholes are forbidden! In particular, the program cannot read any external lookup table.

  • The source code of the program must be shorten than 1024 characters.

The program with the lowest average compression ratio will win.

To determine your average compression ratio, you can to use the following Python script, or write your own equivalent program. Here is the list of 1000 random numbers.

import random

def f(x):
    # edit this function so that it will return 
    # the output of your program given x as input
    return "1 + 1"

random.seed(666)

S = 1000 # number of samples

t = 0.0

for n in xrange(0, S):
    # pick a random decimal number
    x = random.uniform(0, 1000)

    # compute the compression ratio
    # length of output / length of input
    r = len(f(x).translate(None, " +-*/^()")) / float(len(str(x).translate(None, ".")))
    t += r

print "Your average compression ratio is:", t / S

Good luck!

NOTES:

  • Whitespaces in the output are not mandatory. Strings like 1+1, 1 +2, or 1 + 2, are all okay. Indeed, the script to compute the score does not count whitespaces and parenthesis in the length of the output. However, note that the use of whitespaces is necessary if you choose Polish or reverse Polish notation.

  • Regarding the usual infix notation, the precedence rules are the following: first all exponentiation (^), then all divisions (/), then all multiplications (*), then all additions (+) and all subtractions (-). But I do not know how much this could matter, since you can use parentheses.

  • A way to edit the function f in the script above can be the following, however I think that it depends on your operating system; on GNU/Linux it works. Name your program "inverter" (or "inverter.exe") and place it in the same directory as the Python script. Your program should get X as the first argument of command line and return the expression in STDOUT. Then edit f as follows:

    import os
    def f(x):
        return os.popen("./inverter " + str(x)).read()
    

EDIT: As a consequence of the comment of Thomas Kwa, now the operators do not contribute to the length of the expression. The challenge should be more "challenging".

\$\endgroup\$
  • \$\begingroup\$ 1. I've replaced most double quotes with backticks, since I think that it improves readability. If you disagree, feel free to roll the edit back. 2. Multiplication is missing from your precedence list. It matters because we have to account for parentheses in our 1024 bytes of code. \$\endgroup\$ – Dennis Jan 16 '16 at 17:13
  • \$\begingroup\$ @Bob: regarding the rule change about accuracy: "agree with all the digits", does it mean that if X = 5.23 a value of 5.2301is ok, but 5.2299 not? \$\endgroup\$ – nimi Jan 16 '16 at 18:36
  • \$\begingroup\$ @nimi Yes, 5.2301 agrees with all the digits of X = 5.23, while 5.2299 does not. \$\endgroup\$ – Bob Jan 16 '16 at 18:47
  • 2
    \$\begingroup\$ This will almost certainly be won with rational approximation. There's no other way to get sufficient entropy to catch enough numbers when extra space is spent on operators. \$\endgroup\$ – lirtosiast Jan 16 '16 at 19:40
  • 1
    \$\begingroup\$ This is more like RIES than Plouffe's inverter. \$\endgroup\$ – Peter Taylor Jan 16 '16 at 20:02
3
\$\begingroup\$

Haskell, 1.08404005439

import System.Environment
import Data.Ratio
import Data.Lists

main = do
   arg <- fmap head getArgs
   let number = read (arg ++ "5")
   let (_,_:decs) = span (/= '.') arg
   let acc = (read $ "0." ++ (decs >> "0") ++ "4999") :: Double
   putStr $ replace " % " "/" $ show $ approxRational number acc

This uses the approxRational function which converts a floating point number to a fraction with a accuracy of a given epsilon. It simply returns this fraction. As Haskell prints rationals with a % in-between, we have to replace it with the division sign /.

The accuracy parameter is calculated from the input number. We have to take into account that all the digits have to match, so 4.39 is fine for 4.3 but 4.29 isn't. I append a 5 to the number and the accuracy is a 4999 at the same decimal place as the appended 5, e.g.

12.347       -- input number
12.3475      -- append 5
 0.0004999   -- accuracy epsilon for the "approxRational" function.

E.g. 34.147425 -> 43777/1282.

Edit: the rules for accuracy have changed. The test case includes numbers with up to 11 decimal places and all have to match.

Edit II: it seems that the provides Python script doesn't strip off trailing newlines, so I've changed from putStrLn to putStr.

Edit III: again, new scoring rules

\$\endgroup\$
  • \$\begingroup\$ Nice. I edited my question so that the expression returned by the program should agree with all the digits of X. I do not think this would change your score, however it is better if you check. \$\endgroup\$ – Bob Jan 16 '16 at 18:21
  • \$\begingroup\$ Does Haskell have a way to shorten 0.000001 to e.g. 1e-6? \$\endgroup\$ – ETHproductions Jan 16 '16 at 18:35
  • \$\begingroup\$ @ETHproductions: yes, 1e-6 also works, but this isn't codegolf ... \$\endgroup\$ – nimi Jan 16 '16 at 18:38
  • \$\begingroup\$ Ah, right. But it might come in handy if this gets really long, close to 1024 bytes ;) \$\endgroup\$ – ETHproductions Jan 16 '16 at 18:39
  • 1
    \$\begingroup\$ @Bob: it does change the score dramatically. Now accuracy can be up to 11 decimal places instead of 6. \$\endgroup\$ – nimi Jan 16 '16 at 19:34
2
\$\begingroup\$

Mathematica, 1.1012 1.10976107226107

Rationalize[# + 5 (a = 10^(Floor@Log10@# - Length[First@RealDigits@# //. {a___, 0} :> {a}])), 5 a - 1*^-4 a]~ToString~InputForm &

So far, this has the lowest score! Gives the rational with the smallest denominator given the digits. (Sorry for the unreadability, forgot that this wasn't a golf contest for a minute.) Some testing:

In[1]:= f=Rationalize[#+5(a=10^(Floor@Log10@#-Length[First@RealDigits@#//.{a___,0}:>{a}])),5a-1*^-4a]~ToString~InputForm&;

In[2]:= f[811.359484104]

Out[2]= 9876679/12173

In[3]:= f[0.000000001]

Out[3]= 1/666666666

In[4]:= f[999.999999999]

Out[4]= 2000021150999/2000021151
\$\endgroup\$
  • \$\begingroup\$ Can you add an example? \$\endgroup\$ – Bob Jan 16 '16 at 23:22
2
\$\begingroup\$

Python, 1.25927791772

I'm surprised no one else has tried the obvious approach, which incurs about 26% overhead:

from decimal import *
def simplify(numstr):
    numdec = Decimal(numstr)
    digits = -(numdec.as_tuple().exponent)
    num = float(numstr)
    return '{0:.0f}'.format(num * 10**digits) + '/10^' + str(digits)

This just converts XX.XXXX into XXXXXX/10^4 and so on. For the majority of test numbers, this means converting 12 digits (and an uncounted decimal point) to the same 12 digits plus three more (plus two uncounted symbols).

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

JavaScript 1.7056771894771656

Very simple, very bad score

F=x=>([x,d]=x.split`.`,n=+(x+d),d=+d.replace(/./g,9)+1,G=(a,b)=>b?G(b,a%b):a,g=G(n,d),(n/g)+'/'+(d/g))

test=[456.119648977, 903.32315398, 434.375496831, 500.626690792, 811.359484104, 
553.673742554, 712.174768248, 123.142093787, 814.759762152, 385.493673216, 
629.109959804, 891.825687728, 988.817827772, 16.7651557543, 967.455933006, 
99.3802569984, 681.552992408, 169.770898456, 921.658967707, 610.512640655, 
420.065644152, 702.514151372, 517.04720252, 86.3589856368, 960.117250449, 
311.152728003, 620.240077706, 130.232920047, 901.22564153, 528.511688187, 
50.841278105, 737.146071519, 836.88270257, 13.9544843156, 45.8723706867, 
760.14443626, 256.035110545, 460.972156302, 217.514875811, 34.4165446011, 
426.209854826, 500.979753237, 930.071200996, 751.301967463, 817.525354878, 
918.861794618, 794.520266221, 531.896652685, 419.295924811, 927.526963939, 
989.027382734, 82.1589263516, 965.904769963, 708.295178015, 778.541588483, 
410.404428666, 894.612613172, 470.045387404, 460.773246884, 505.524899467, 
451.852274382, 417.910824093, 883.45180574, 319.767238241, 544.794416784, 
346.361844704, 122.300743514, 517.293385872, 748.134450425, 589.547392631, 
870.937945528, 465.607198253, 379.697188157, 215.095671553, 471.696590273, 
544.827425571, 883.01895272, 514.893297677, 703.800591, 788.816870867, 
777.433484884, 990.615076538, 925.473132794, 494.964321255, 911.643885633, 
103.244050895, 425.938382631, 421.075783639, 363.155392963, 301.617712632, 
268.237096551, 42.0971441114, 252.071029659, 260.398845137, 433.781658026, 
278.550969539, 446.456847155, 466.145132666, 23.1267325005, 92.2303701531, 
792.994090972, 100.482658881, 796.600758817, 786.019664003, 328.859998399, 
390.221668208, 750.32581915, 332.277362524, 983.205082197, 862.001172096, 
823.825060923, 662.455639665, 926.337262367, 618.446017944, 696.465793349, 
408.095136772, 519.31659792, 928.091368548, 177.367743543, 980.822594006, 
401.832552937, 66.1163636071, 127.511709579, 291.85194129, 11.338995907, 
880.568902788, 982.945394792, 491.753920356, 222.011915866, 317.023389252, 
601.694693495, 871.340895438, 427.621115915, 886.273120812, 345.688431619, 
248.992214068, 738.874584632, 109.03516681, 146.362341902, 447.713463802, 
600.947018155, 415.419601291, 369.549014288, 141.697677152, 895.502232931, 
528.201404793, 673.817459041, 215.852364841, 164.552047867, 764.085838441, 
323.70504093, 197.868519457, 759.91813327, 369.341528152, 768.793424447, 
111.674153727, 495.99248701, 363.669738825, 596.082713332, 747.205484326, 
666.879146337, 102.908405893, 424.113319661, 476.379228696, 971.353959219, 
162.634464034, 761.838583493, 767.799964665, 347.294217881, 353.760366385, 
230.905221575, 125.898250349, 565.850510939, 667.61204275, 196.449923318, 
279.792505368, 279.034332146, 533.902967966, 57.688797172, 153.08128158, 
821.993175733, 982.886617074, 433.447389936, 29.0911289168, 442.422057169, 
804.518563086, 500.73307383, 948.932673563, 723.030013363, 572.092408062, 
853.660849797, 481.331513905, 942.064561235, 42.4709711072, 982.87325027, 
352.171583912, 238.247057259, 823.238147233, 526.013997729, 644.51102393, 
366.71793217, 933.49508788, 903.534625763, 857.169528071, 735.780465845, 
378.732263357, 12.1875971069, 964.370964223, 419.654315024, 705.414457347, 
353.953487281, 501.657967991, 849.706011343, 713.414932699, 827.420809946, 
596.719004174, 609.780183857, 826.546581587, 76.33513551, 0.500492073649, 
627.694684485, 186.236492637, 360.200893605, 478.625892592, 229.111877611, 
423.754891888, 657.973373515, 16.9761882463, 974.491769915, 945.864753785, 
237.454051339, 179.687469205, 418.658590265, 714.833543375, 318.816023475, 
650.727666516, 488.596054138, 987.542619517, 216.006047902, 80.7125255243, 
144.181653533, 266.522883823, 818.574355104, 600.21171237, 895.307289865, 
198.329664663, 124.824876993, 31.1227116403, 541.348603643, 542.257190363, 
304.231517157, 506.706000025, 84.9413478067, 170.491409724, 229.013799764, 
671.014301245, 87.1441069227, 763.676724963, 742.639944243, 435.559778934, 
383.882521911, 238.741657776, 647.17907848, 927.512981306, 549.612975568, 
791.443454295, 701.809936899, 987.551368536, 91.3122813408, 398.587619734, 
847.240295481, 470.53644512, 507.410113063, 540.35838629, 637.883207888, 
982.322584309, 975.975221911, 371.493982019, 172.638439006, 747.126873375, 
99.5418242164, 309.903703204, 640.628684948, 314.750618166, 146.000991772, 
384.388581648, 217.815818267, 733.571499911, 690.506791178, 945.671862182, 
344.854300466, 66.9720187046, 600.727439672, 98.4760964868, 295.60483304, 
478.855074245, 490.351187811, 479.533769337, 239.205093033, 58.7686847649, 
375.442162104, 615.561415277, 974.347539912, 743.935932659, 210.319831557, 
782.442881822, 556.123534411, 774.571029531, 821.094541585, 782.478179678, 
123.630035193, 652.088033798, 753.122074115, 303.840694329, 449.088557671, 
38.4843483532, 173.031570335, 728.973326841, 226.816627623, 119.472479023, 
705.899011665, 927.865200825, 157.998809157, 327.490515863, 225.137067487, 
501.556087254, 167.031923234, 396.975128016, 826.305341676, 396.340544863, 
569.58630546, 694.788762272, 10.1343501944, 369.36109683, 29.8034453658, 
916.970188353, 985.814850566, 888.359275561, 689.939392935, 409.116566134, 
144.938228502, 67.8210674843, 870.61549803, 563.639796984, 431.618386108, 
145.691380363, 350.505911146, 326.638836654, 708.160936271, 345.738257395, 
159.932627655, 311.885663889, 229.603462168, 110.746858295, 517.566252532, 
231.2683822, 908.329966697, 999.286952896, 700.486300449, 532.543272168, 
548.536320153, 248.586068291, 844.156717745, 477.281959996, 964.072712855, 
157.863146561, 919.917761996, 187.741733233, 358.474587832, 541.364663045, 
297.862474812, 673.876495999, 641.468684483, 934.366789232, 112.750864631, 
179.36727691, 744.421362119, 954.914513373, 356.362877284, 642.423557253, 
835.156704382, 145.847575914, 917.085464611, 633.00944503, 4.20412765537, 
577.177004175, 774.63403371, 846.937269117, 978.134451441, 927.806763324, 
3.39763102303, 650.528163199, 347.525631206, 378.956292306, 266.22945414, 
175.085055263, 571.539823838, 274.670508282, 835.348780918, 190.612093018, 
425.355323169, 283.050471535, 573.262462068, 236.809923974, 86.5812138421, 
442.645729259, 376.598156438, 412.17611326, 575.13654395, 76.4906160271, 
382.261334337, 419.108062252, 413.347694426, 726.1697083, 738.059837008, 
228.479265313, 982.210601477, 693.205052764, 788.820483643, 279.491316277, 
381.050856949, 914.836538216, 369.451591691, 828.975002455, 33.0866822761, 
552.943575842, 229.194581446, 900.603947989, 697.081349116, 38.8501269177, 
599.81038281, 199.242914298, 565.383604483, 241.671424615, 874.199638779, 
294.933677019, 238.713921761, 953.886254575, 126.3147347, 156.308580451, 
1.01666626965, 410.067483484, 969.052527031, 184.927913357, 282.530928636, 
204.745328524, 450.670433109, 129.119772077, 581.256246505, 6.84233762299, 
39.4666067908, 865.975624765, 868.401636982, 114.207339514, 921.542812579, 
435.593193085, 346.934279797, 830.059520451, 691.952980275, 694.258623119, 
548.775134898, 527.057955887, 267.64250387, 113.091700858, 210.713307935, 
253.707632265, 832.083850441, 455.161145588, 403.528402677, 237.983049672, 
903.782609365, 314.331975332, 209.862002009, 488.057537383, 905.587478495, 
929.797161232, 325.793664626, 734.098176437, 519.087164488, 555.076580313, 
97.8973027155, 260.92615898, 391.460005616, 187.462694014, 660.460370626, 
861.783280209, 751.657352012, 528.280341385, 943.741294674, 204.705877292, 
106.65265656, 17.8070044565, 233.101412197, 38.2613365534, 729.385921979, 
773.529715946, 429.882870272, 166.782428109, 738.061383178, 381.289974545, 
425.98872381, 405.120420988, 672.370449304, 276.696982879, 640.620718977, 
244.652935713, 43.3611372718, 611.721720179, 552.336391617, 939.435275549, 
337.333914132, 88.3768763311, 537.456873711, 98.6468535441, 601.024140128, 
526.374477437, 959.339713851, 794.438445711, 419.365144317, 128.425263651, 
894.306756225, 750.689349267, 849.804073407, 144.580034264, 5.21870382078, 
316.954557791, 258.037070914, 907.185890899, 821.078874769, 73.0065239329, 
902.397997543, 623.811378865, 278.742785334, 546.742289504, 306.338798014, 
624.510083572, 278.778694986, 992.433419109, 568.791129496, 800.987198104, 
817.781503455, 364.391142069, 229.768701593, 791.500313449, 523.97492671, 
711.79222697, 841.514367793, 811.043873744, 312.112640331, 344.686366808, 
362.852877349, 908.102021975, 77.1500991776, 383.192419609, 686.951731951, 
220.529025627, 867.530056756, 14.3366282672, 408.594160445, 123.165786631, 
998.59134116, 548.326927924, 94.1928597561, 324.065711084, 731.488189617, 
665.464202995, 306.278211631, 986.173950386, 627.219661146, 333.954277825, 
90.2956353646, 162.227112949, 272.511457828, 857.528739452, 503.843643462, 
576.629152535, 548.024554676, 363.491120268, 679.874538441, 583.700940158, 
106.952792329, 9.38392100562, 338.353858169, 293.571162077, 804.681145319, 
767.462050744, 313.643862301, 468.190192547, 572.949085984, 350.221796616, 
917.105455473, 303.54853149, 391.390619956, 504.247647998, 93.0135480388, 
246.512166315, 908.97228941, 943.218403856, 530.309445245, 309.754887232, 
959.789201543, 970.486542083, 797.580736004, 290.319550119, 846.108212188, 
532.653666441, 887.339176163, 679.691675058, 912.533817736, 920.067525894, 
222.511534133, 96.2743176283, 21.4898199044, 77.2132479765, 371.345880832, 
436.959444929, 215.804186286, 399.231434773, 621.793520068, 670.184752989, 
898.150427875, 223.481192922, 886.318270113, 516.799097006, 533.999918536, 
713.480918784, 917.832970718, 372.788549636, 628.966711322, 944.179767515, 
192.101163486, 343.997422161, 804.100009349, 931.645390583, 990.171180084, 
260.766724798, 785.681499223, 356.704428677, 700.517830816, 951.584623525, 
144.084686297, 259.528412476, 171.745260869, 139.015277926, 901.447521593, 
620.501210347, 151.032781338, 46.1159165911, 425.230998623, 894.613060967, 
625.179508617, 242.868974022, 106.982050541, 301.464135508, 573.158784529, 
688.278622585, 464.999428923, 322.662480912, 110.118666284, 731.557589997, 
946.121567036, 495.536592777, 721.786554826, 401.204812967, 523.199107158, 
941.414041302, 13.1534875549, 156.596310513, 983.985066957, 371.429892366, 
597.927750948, 983.992168593, 170.977999856, 83.6807794877, 817.971626168, 
516.088416242, 827.937736139, 859.209288785, 615.315584986, 609.792111637, 
554.693516004, 470.967675734, 223.237818744, 990.385531141, 530.824138102, 
909.365555497, 994.864631519, 997.447332309, 328.212731713, 307.035914722, 
409.123485776, 799.130975525, 967.234526581, 959.671441584, 353.229298604, 
420.982728285, 76.7863969552, 28.5449571984, 210.265549753, 913.543941547, 
315.091741118, 662.094750123, 852.203603892, 298.207293217, 509.30012338, 
65.7679645109, 621.200794815, 935.510670259, 779.330025526, 937.283929747, 
756.173490123, 733.792396159, 795.211149457, 302.088313881, 570.641269144, 
757.135463505, 242.60845981, 457.593727034, 225.360079221, 142.221548109, 
17.6336964488, 360.261380451, 623.475218825, 692.670820913, 584.185971173, 
662.861929515, 276.807298644, 480.122225367, 954.608081636, 627.928577217, 
459.835351987, 485.168643598, 793.612119132, 654.855590208, 271.958933288, 
969.652698005, 976.785064283, 505.116414306, 797.184208528, 628.943525947, 
959.160096155, 663.113680213, 768.371354051, 590.4585491, 773.296754989, 
407.351603593, 88.0630070991, 905.529072694, 340.59794601, 439.12099902, 
233.540790202, 364.088450076, 470.123174021, 102.448882161, 608.789225571, 
392.768415134, 713.100614552, 209.2003898, 62.2154487033, 372.921756097, 
492.623365519, 581.128110129, 820.570542768, 339.686321984, 713.824072462, 
999.045113081, 306.938298797, 184.480805204, 465.144186806, 753.870865996, 
78.4248974773, 914.793550949, 952.526126809, 745.524994917, 138.306312094, 
727.779875346, 561.393678162, 772.777064716, 72.7542234799, 504.766493657, 
753.225048814, 171.848362302, 941.292665664, 441.751526079, 63.0349316166, 
535.273783514, 629.040768898, 808.08324249, 457.787416804, 187.372504534, 
418.1266562, 433.695070727, 776.092568964, 211.004041498, 740.766035298, 
816.391594543, 458.991042003, 94.0308738235, 624.589391691, 118.430830788, 
178.888039553, 905.16710481, 148.542033271, 962.242139722, 35.5229349814, 
716.472840429, 587.99823034, 252.557765324, 37.8879245566, 399.689202524, 
383.425506008, 464.748020898, 308.786698798, 583.669994119, 231.746308268, 
524.76171028, 897.374397044, 577.218755662, 562.645278506, 434.940887118, 
254.327344231, 540.874257344, 123.680835723, 539.503191151, 816.484752836, 
961.415099734, 349.660216271, 596.159995894, 595.762432693, 955.539005194, 
687.809440375, 571.725613886, 308.13021345, 617.471476595, 701.003582396, 
3.96581420188, 185.987820184, 48.1246847598, 539.131050625, 989.571379915, 
249.821643429, 725.895300104, 711.034103146, 74.8291260662, 721.572101122, 
142.992636014, 419.591421178, 984.914852359, 36.7363617464, 133.19819475, 
380.054235605, 692.83285665, 827.597995374, 995.818667532, 126.589103128, 
682.800070236, 466.330036969, 302.143073837, 786.240218566, 299.551583986, 
430.07770804, 483.534119703, 473.617334239, 1.64416431436, 953.126991927, 
251.892147628, 366.320222366, 137.6878957, 287.000037146, 348.549654758, 
55.6668003422, 65.1444653143, 810.336733005, 247.448273359, 514.541152359, 
545.299341596, 740.254480746, 607.431747363, 176.075079982, 922.502042696, 
585.799132666, 5.53670276888, 304.467968825, 298.915106192, 561.78882135, 
42.5914472262, 486.800635021, 61.0833598622, 944.347739678, 668.746271709, 
756.586266764, 408.787974993, 161.622855, 76.9222121123, 273.398447299, 
224.158188706, 869.44674983, 58.3114312618, 490.559449132, 439.137943547, 
816.959032357, 73.0577752895, 613.711059891, 899.395509193, 230.235211112, 
651.089914878, 418.795635547, 873.424446884, 897.792771782, 704.102385815, 
518.126528796, 545.099037865, 104.410545145, 416.115870896, 617.579630637, 
333.700660761, 698.454752336, 323.794560581, 614.778464988, 978.982432433, 
656.459219246, 311.387615291, 262.993283002, 98.703803798, 316.038737757, 
511.251635007, 597.716611457, 837.873132231, 985.745340467, 653.714321915, 
759.002380543, 257.908251778, 764.546995782, 336.260865935, 746.604123567, 
640.209566004, 448.844970845, 925.255475065, 972.485574416, 47.0841050739, 
231.133339622, 994.520385942, 766.591528041, 355.476025092, 325.525579517, 
591.707824382, 302.51618806, 250.791496027, 325.751078168, 148.78604636, 
488.176440838, 760.361648381, 213.189413642, 509.565395067, 284.468094856, 
567.126065507, 828.024492382, 938.902419548, 141.420420877, 719.989392811, 
854.189823836, 545.746745299, 713.177111859, 800.749418944, 217.781813549, 
692.416094897, 703.129981045, 607.928079305, 876.072026145, 983.933471359, 
824.755945781, 472.143208136, 22.2541577801, 640.071388089, 52.8148724127, 
646.607940231, 228.870749952, 824.59255967, 20.4078078906, 211.860134988, 
176.392620646, 786.744977859, 983.183973543, 738.585099683, 75.976724176, 
49.4604753001, 628.2042889, 991.358549436, 526.125428702, 836.487360003, 
216.533860839, 654.106395874, 65.4049854833, 858.352891393, 777.146190395, 
630.588944701, 141.352770092, 501.454292251, 792.956685991, 709.053823609];

console.log=(...x)=>O.textContent+=x.join` `+`\n`

console.log(test.length)
var r=0
test.forEach(v=>{
  v=v+''; // to decimal string
  var x=F(v);
  check = v==eval(x)
  if (!check) console.log ("Error",v,x,eval(x));
  else 
    // console.log(v,x),
    r+=x.length/v.length
    
});
console.log(r/1000)
<pre id=O></pre>

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

Python, 1.9901028749

Continued fractions turn out to not be a serious contender, unfortunately.

from fractions import *
def simplify(numstr):
    frac = Fraction(numstr)
    terms = []
    while frac>0:
        terms.append(int(frac))
        frac -= int(frac)
        if frac > 0:
            frac = 1/frac
    for n in range(0,len(terms)):
        temp = 0
        for i in range(n,0,-1):
            temp = 1.0/(terms[i]+temp)
            # print i, terms[i], temp
        temp += terms[0]
        # print repr(temp)
        if repr(temp)[:len(numstr)] == numstr:
            break
    return '+1/('.join([str(x) for x in terms[:n+1]]) + ')' * n

examples:

141.352770092 141+1/(2+1/(1+1/(5+1/(20+1/(20+1/(1+1/(1)))))))
501.454292251 501+1/(2+1/(4+1/(1+1/(31+1/(1+1/(4+1/(1+1/(1+1/(2)))))))))
792.956685991 792+1/(1+1/(22+1/(11+1/(2+1/(6+1/(1+1/(2+1/(1+1/(2)))))))))
709.053823609 709+1/(18+1/(1+1/(1+1/(2+1/(1+1/(1+1/(1+1/(10+1/(58)))))))))
\$\endgroup\$
0
\$\begingroup\$

Python, 1.10900874126

Actually evaluating the continued fractions in my previous answer yields the equivalent of @LegionMammal978 s Mathematic answer, which I think is the naive optimum. Doing better than this will require getting creative with representing the integers, possibly including searching for sub-optimal fractions to get to easier-to-represent integers.

from fractions import *
def simplify(numstr):
    frac = Fraction(numstr)
    terms = []
    while frac>0:
        terms.append(int(frac))
        frac -= int(frac)
        if frac > 0:
            frac = 1/frac
    for n in range(0,len(terms)):
        temp = Fraction(0)
        for i in range(n,0,-1):
            temp = Fraction(1)/Fraction(terms[i]+temp)
            # print i, terms[i], temp
        temp += terms[0]
        if repr(float(temp))[:len(numstr)] == numstr:
            break
    return str(temp.numerator) + '/' + str(temp.denominator)

examples:

141.352770092 == 1992650/14097
501.454292251 == 5041120/10053
792.956685991 == 33373961/42088
709.053823609 == 154592878/218027
\$\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.