12
\$\begingroup\$

A simple register calculator

This challenge involve a simple register calculator that works in the following way:

  • It has some registers named A,B,C,...,Z, each of them can contain an integer, they are all initialized to 0.

  • It executes instructions of 3 characters: The first character of any instruction is one of +,-,*,/,= (add, subtract, multiple, divide, copy), the second character is the name of a register, and the third character is the name of a register or one of 0,1. The meaning of the instruction should be quite clear, here some examples:

    • +AB means "set the value of the register A to the result of A + B", and similarly for -AB,*AB,/AB. The division A / B is done as in C.
    • +A1 means "increment the register A of 1", and similarly -A1 decrements A of 1.
    • =AB means "copy the value of B into the register A, similarly =A0, =A1 sets A to 0, 1, respectively.
  • It takes as input a string of consecutive instructions and it returns the result of the last operation, some examples:
    • Given =A1+A1*AA it returns 4.
    • Given +A1+A1=BA+A1*AB it returns 6.
    • Given +A1+A1+A1*AA=BA-B1*AB it returns 72.

It is easy to write such a calculator in your preferred programming language, here an example in Python:

def compute(cmd):

    opr = {"=": lambda x, y: y, "+": lambda x, y: x + y, "-": lambda x, y: x - y, "*": lambda x, y: x * y, "/": lambda x, y: x / y}
    reg = {"0": 0, "1": 1, "A": 0, "B": 0, "C": 0, "D": 0, "E": 0}
    ans = 0
    i = 0

    while i < len(cmd):
        op = cmd[i]
        r1 = cmd[i + 1]
        r2 = cmd[i + 2]
        reg[r1] = ans = opr[op](reg[r1], reg[r2])
        i += 3

    return ans

The challenge

Write a program in any programming language that takes as input a positive integer n and returns a string of instructions that the calculator described above evaluates to n. For example, given n = 13 a valid output for your program could be +A1+A1+A1=BA+A1*AB+A1. There are some restrictions:

  • Standard loopholes are forbidden.
  • The source code of your program should not exceed 1024 characters.

How to compute your score

Run you program on each of the following 1000 random integers and sum the total number of operations in each output. For example, +A1+A1+A1=BA+A1*AB+A1 consists of 6 operations, note that the copy instructions = are NOT operations and you should not count them.

3188162812
3079442899
158430004
2089722113
3944389294
2802537149
3129608769
4053661027
2693369839
420032325
2729183065
4214788755
680331489
3855285400
4233942695
4206707987
2357544216
457437107
2974352205
3469310180
3552518730
4140980518
2392819110
2329818200
662019831
2841907484
1321812679
2853902004
2272319460
133347800
1692505604
2767466592
3203294911
1179098253
2394040393
2013833391
3329723817
977510821
2383911994
1590560980
2045601180
1324377359
1586351765
1604998703
3016672003
3653230539
1466084071
2746018834
1056296425
3225491666
2113040185
918062749
3506683080
1809626346
3615092363
3944952222
4281084843
137951018
577820737
2304235902
4143433212
3183457224
294693306
1680134139
689588309
3657258008
2664563483
628899295
886528255
2539006585
2767153496
2742374091
2927873610
3725967307
2252643563
2716697503
1098010781
895335331
305272851
2605870648
3473538459
2739664556
2127000353
1774191919
3239195523
3120846790
3239808174
2588745068
3363081711
3105613110
3443977876
3233369379
949558184
2159450658
2930876206
1714955144
712790171
2472327763
3524210951
24655707
754856403
3220292764
708275816
2369186737
2485130017
404438291
1444836457
3936354990
3488645083
3881548856
1385884481
3750970390
1355492018
4246667593
791749996
1768738344
4014670055
3594141439
3111942631
2763557857
250495911
1635747286
1397550167
35044748
826650975
1249876417
2756572453
2014910140
1934230545
3893965263
1921703452
3479225211
232639352
1205471850
3147410912
4161504178
3896565097
336993337
898565456
1377983619
627866260
2972370545
2867339047
1517056183
3113779980
3650970589
105184832
3785364530
1892053898
2844419064
3581584776
773357885
1635965442
579795505
1082737975
4177210361
33726403
500010881
3770114942
1949554222
1808394144
2552929558
1679344177
4127951276
3703470385
2167661112
2012330972
3330988942
1625024662
4028645080
2268576559
1122753547
2801157103
2297468355
1248325165
3040195088
1505917132
1975920989
1331044994
1060195583
4053434779
1711909914
4165818150
1144987338
2582851730
159607843
4224173218
1122473605
4137009351
1859108466
140046799
3608276151
3755161872
1715239079
2210528921
4149673364
1683676925
3555426962
1903470380
1647594563
3992028616
831939758
1940233614
616234640
1033981562
989110726
3308560842
1362495884
2271865210
2497232294
2166547324
3134965769
1407359056
184303653
876724554
2257276636
1339263453
1505646879
4103125312
602341088
3411146479
4076735898
988798982
2881621101
3835638677
350262003
2083944362
793689959
1796614310
1722728365
1419496784
311460422
988078714
1191131280
685548336
2073528073
1341976830
1380421367
854492684
2349152
2760841279
3512440862
3492462961
955419776
134666263
1515743147
2802649615
343970838
5900423
3640581071
3690344254
33097513
3453017483
2702390881
2881748921
488817210
3179354661
3029418544
70044411
1956963103
1138956191
4099413570
113469500
2905850103
2267006431
990605747
2016466413
1406729175
457735529
1987564886
2555785209
2550678495
1324710456
1215784300
717815828
1894258881
2929394992
2793836849
1428923741
633224565
3516183531
221895161
2798935778
517240774
1906654368
3577752510
1412213936
978042011
741638677
1565247138
2333064112
2549498124
212184199
1539484727
3421514248
1918972072
933315257
1744663538
3834248593
1024107659
112895438
3354823598
3126205726
375723484
2105901209
287450971
669099946
1397558632
2606373532
125689337
3717502670
3258204174
1650199158
600374361
368452551
3686684007
3030953879
492919617
1203996049
863919924
2155962926
2878874316
1081637213
4025621502
969421830
906800845
732593812
3705231669
100350106
2062905253
2394749290
1537677769
2230238191
447840016
1442872240
2024556139
3023217942
4009927781
643221137
1779666873
3953330513
2024171749
795922137
997876381
1924314655
1177794352
3951978155
2649627557
1497778499
1718873438
1921453568
1327068832
2832829727
2225364583
1476350090
2647770592
3820786287
916013620
3982837983
3614316518
308109070
1800544679
2981621084
1428321980
4050055605
1492289670
2386916424
3191268731
580405899
2267245329
1732073940
1096029767
1295821464
3364564864
2652920150
3364522304
488005592
2192878399
160846995
218793067
300953008
3159368600
3645636269
2691580186
827223351
3050975392
1465133880
1478016997
1719998613
652363401
2555898614
4066532621
1765212455
34216921
1638964775
1371429240
838490470
82423487
1714800592
3494875381
3873346547
4054782046
3696936256
4275305812
2168667803
4160190912
3795501892
1459579204
3788779072
265527890
854488955
2942834006
2379627823
518232762
518434777
3944651255
3797616526
3707541025
322349517
474725696
3644506417
298197509
2568152353
2590844880
3117635513
1074315194
4084685556
2962342284
2653600388
3288534723
3794138452
1647860359
4009971876
2133083710
3370033103
47844084
1104447774
1945114365
3574343235
3780282459
3381199373
1018537272
1382098367
1412005134
1344062628
2346644176
722899092
2614932463
2145401890
827890946
255045026
1886847183
2717637818
1153049445
1367369036
2426902133
1836600086
3249356599
3406700718
2782602517
805660530
2582980208
2668716587
1318623475
3718765477
3906582528
2049615170
2266673144
693017899
1850804437
3662076224
1439399599
3609671497
3521926429
661675539
3211764017
3849411286
3961495122
3240515755
3110520252
3247223395
2601642984
531083777
1428656097
2621375427
1425006097
3346815151
1736182994
2749088925
3828456894
522766581
1596198864
1089234568
516631143
1714958540
550383692
2205580129
1129010921
2855807192
843448099
2537619198
2817077189
1862738454
1292393032
1867270512
3245153467
1330535377
63085178
476740794
3784629223
1469948976
2840691011
1501561593
2222500334
1417999206
1501666518
1146520258
853475958
688318779
2212745726
3697365636
4188412866
1971070414
2765322323
3338736319
4106229372
3547088973
3610171853
417218792
2645989082
2625322695
3788226977
866881900
3042410163
3339075441
1434921464
2037891551
4265507318
1488099724
573885128
528293886
863928770
2214944781
3913280213
3752689511
3519398632
549671367
662190591
3578320334
1609736323
1920189717
2049295962
1680309555
3056307661
237881083
1746281815
3988208157
2505692550
533953235
3859868829
3792904168
3181176191
764556169
78617399
3222196435
2366977555
608590681
303423450
559903926
1444205960
2795852572
3461738581
2509323146
2734638697
118860267
1918139288
2567665860
2153622033
3097512138
4224583193
1308314884
1348993134
3573313872
80532767
373807250
3963872687
1414605355
1390608957
1438723366
3335250816
3812365414
1257060108
1155935111
2101397457
1834783042
1751275025
1697354321
2932378401
1665717453
1378885897
3863913849
169333097
1073827664
777437131
3466174585
4046814722
2525749031
2116514103
2240001267
3455152569
579339098
2014028365
3808320943
1577950380
2691778801
3752766002
3849855789
1537004930
384431257
2179992010
36153591
4192751001
1804838630
987326618
4149586235
2231006803
3583701679
820347619
316668661
709355791
3570998394
1949820944
2602827205
4168457060
4281494037
3371936535
2794977651
2859282911
3673967898
13357998
1321990240
1432920498
2348123485
205633677
1467790392
3366396640
382875586
3791338683
478208002
2728443830
2837394277
3723656578
289818980
3607540282
1775363546
2183739548
4177115501
775276465
1690545788
1075449013
572714464
2769169223
3277515030
3206017211
763710358
2535539628
538656028
1428522787
2412864965
2447537924
3399886379
1955069748
73813115
2985639257
3129134081
2902917098
3832348869
2446124823
1520308572
2779582451
3152572003
284626848
2622927684
2243844449
2707184379
3996077339
1143205932
4249437886
4013946423
1243498130
2239561716
2454002725
3202102404
3489290520
568827898
2077682453
1973647425
2311090024
3452693414
566624799
1905493748
3381640023
3228957600
2097911855
3346084948
2492783447
2933529940
2933060277
509789087
4110089257
2789615392
2293641703
3346767700
2861425094
1325878754
2100601638
3154735442
1589556635
543727545
2077077585
2301440962
3562819978
3678224450
88375847
2286883432
810549767
4111034512
672827645
3538058849
3243887391
4260719631
3878976366
1173949115
522599614
2237854030
3700071391
3701211843
2474968151
1856102230
1612779479
417924004
1408725257
3663088753
1092263738
373569884
1394203899
2687184291
2200173651
16483411
2144831293
1953173328
2680701575
1891347549
594615324
2941482356
1349499420
2341998425
3246298001
3915604073
2598997329
2742107968
1706515316
3230227853
1698480626
3171621896
3553701103
3699504403
3264436517
789435265
1540974002
76880268
2021546521
228600347
3120127535
855819397
913492933
1706352147
3824217844
4254086533
4210176230
247387836
3028729765
1294455673
832399118
1989368151
3843532893
4058042419
4176223654
1871853736
2245388136
3396787616
453433399
3628835268
13531968
1038657709
2005262423
409396841
3236752715
504051173
1284135365
1498489066
1951495621
785956452
979254655
1255744440
2124184282
1791931889
2785197261
941345859
2272057653
105734226
1038331147
3859502227
1364397134
1151431380
3572487724
3440271596
3567083908
3969594482
2717167268
2070800249
565656056
2585323347
3710407107
1655322191
2871691151
1578274901
925898023
98152205
2387892947
3688205134
1060122118
3601926463
3963544592
2836575178
3517776876
1116673438
4141604495
3702313624
3321374643
3027449932
446202974
2704262583
1454829930
310100992
4167677094
4283752410
3749990846
3082431927
3668805960
4197104147
2921050366
40497657
1198947069
4265036060
3094866761
732821358
3734577383
3582534668
1453076357
881135315
3444396361
3113501566
2961866531
3235889511
2927326630
151940017
498024918
427292182
4276572621
2573590608
901394328
2351057309
1560851771
836443396
702781140
4143407241
3833119244
1092986235
3835147739
2801574120
2220928350
2773965488
1092717858
2314157136
4281370255
1044194898
4056801311
2672327460
2464844936
2964067147
535238874
34767265
4052881906
277239886
3205998707
4168364957
3390679324
3154285793
3493261782
1364027732
633131904
2306043313
253100060
3085422190
1571296680
1116733249
517969149
2063982173
1580514293
2306636650
211667764
43257052
2187912911
1419556982
2885452390
475014467
4276725894
2112535198
1381468052
3535769995
3030340194
2554618335
701632787
3621637286
200999835
2299787216
148189901
476612087
3139125858
1721355976
2863292989
270189306
1574116759
4001329945
616943685
3636040393
1361384267
1959022335
122277322
2067861043
2294386020
1121565222
1844367203
3119120617
1420612680
1541302975
3197481918
648483752
451388069
856130175
2960393334
988907653
1730735603
1640257249
1832729474
306034410
853922102
2001624344
3253510094
3906676405
37452680
3779097581
1958179154
2395885855
800614078
2085912
3020166783
2260099399
3490922778
2459139074
3886269878
3341685647
1050712773
59317986
3041690572
3236133509
2401182200
1535265086
1663785422
3664887088
3252400434
377629836
1024996414
1518007563
1821746700
1231613438
1709191483
2422047361
1393454235
2346354546
3263498417
3321719966
3652825361
948364811
371026554
2175702095
1880788290
4214724129
503657540

The same list of numbers can also be found on Pastebin.

The lower your score is, the better it is. Good luck!

NOTES:

  • I choose random integers between 0 and 2^32-1, so that computations could be performed in C (unsigned long) or other languages without native support for arbitrary sized integers. However, be careful of overflows!

  • When computing your score, check also that the output of your program is correct, it's easy to make errors.

  • I wrote a script of 512 characters that got a score of 27782.

\$\endgroup\$
  • \$\begingroup\$ Are we limited to the 26 capital letters of the English alphabet, or can we use others (like lowercase letters)? \$\endgroup\$ – Kevin W. Jan 18 '16 at 20:39
  • \$\begingroup\$ @KevinW. lowercase letters are fine too. \$\endgroup\$ – Bob Jan 18 '16 at 20:42
  • \$\begingroup\$ Does +A1*A8 evaluate to 8? \$\endgroup\$ – GamrCorps Jan 18 '16 at 20:57
  • \$\begingroup\$ @GamrCorps No, the third character of any instruction can be only a name of a register, or 0, or 1. So *A8 is not a valid instruction. \$\endgroup\$ – Bob Jan 18 '16 at 21:09
3
\$\begingroup\$

Java, Total Score: 46009 operations

Saved 2000 operations thanks to steveverrill and 1000 thanks to Bob!

z->{String s=Integer.toBinaryString(z),r="=A1";for(int j=s.length()-1;j>=0;j--){if(s.charAt(j)=='1')r+="+CA";r+=j>0?"+AA":"";}return r;};

Test it with this full program:

public class Calculator {
    public static void main (String[] args) {
        A a = z->{String s=Integer.toBinaryString(z),r="=A1";for(int j=s.length()-1;j>=0;j--){if(s.charAt(j)=='1')r+="+CA";r+=j>0?"+AA":"";}return r;};
        System.out.println(A.a(117));
    }
    public interface A {
        void a(int c);
    }
}

Caculates the strings based on the binary representations of the input numbers. Score calculated with this program:

public class Calculator
{
    public static void main (String[] args) throws FileNotFoundException {
        FileInputStream is = new FileInputStream(new File("test.txt"));
        System.setIn(is);
        int c = 0;
        Scanner input = new Scanner (System.in);
        while (input.hasNext()) {
            c+=s(new Long(input.nextLine())).length()/3-3;
        }
        System.out.println(c);
    }

    public static String s(long z){String s=Long.toBinaryString(z),r="=A1";for(int j=s.length()-1;j>=0;j--){if(s.charAt(j)=='1')r+="+CA";r+=j>0?"+AA":"";}return r;}
}
\$\endgroup\$
  • \$\begingroup\$ Good. Looking at the binary expansion is the first non-trivial idea, but it can be improved a lot. For example, this performs bad when n has a lot of 1's in its binary expansion. \$\endgroup\$ – Bob Jan 18 '16 at 22:12
  • \$\begingroup\$ Instead of *AB you can do +AA. then you won't have to initialize B. \$\endgroup\$ – Level River St Jan 18 '16 at 22:12
  • \$\begingroup\$ @steveverrill good idea! \$\endgroup\$ – GamrCorps Jan 18 '16 at 22:14
  • \$\begingroup\$ It is better to initialize A with =A1 instead of +A1, since = does not count as an operation. \$\endgroup\$ – Bob Jan 19 '16 at 8:52
1
\$\begingroup\$

Since the question got some votes, but only an answer was posted since so far, I post an answer (but not the 512 characters / 27782 score mentioned in the question).

Python, Score: 35238

def f(n):
    cmd = "=B1=C1+C1+C1"
    while n > 0:
        r = n % 3
        n /= 3
        if r == 1:
            cmd += "+AB"
        if r == 2:
            cmd += "-AB"
            n += 1
        if n > 0:
            cmd += "*BC"
    return cmd

The idea is the same of GamrCorps's answer, but instead of using binary representation I used balanced ternary representation.

Why does it work better? Because a positive integer n has approximately log(n)/log(2) digits in base 2, and on average half of them are 1's and the other half are 0's, hence about (1/(2 log(2))) log(n) = 0.72... log(n) instructions are required. In ternary balanced representation, n has about log(n)/log(3) digits, on average a third of them equal to 1, and another third equal to -1, hence about (2/(3 log(3))) log(n) = 0.60... log(n) instructions are required.

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