20
\$\begingroup\$

Challenge

Write a function or program which takes a positive decimal number, call it A, and output two positive numbers, B and C, such that:

  • A == B bitxor C
  • B and C must not contain any of the digits 0, 3 or 7 in its decimal representation.

Examples

>>> decompose(3)
1, 2
>>> decompose(7)
1, 6
>>> decompose(718)
121, 695
>>> decompose(99997)
2, 99999
>>> decompose(4294967296)
4294968218, 922
>>> decompose(5296080632396965608312971217160142474083606142654386510789497504098664630388377556711796340247136376)
6291484486961499292662848846261496489294168969458648464915998254691295448225881546425551225669515922,
1191982455588299219648819556299554251659915414942295896926425126251962564256469862862114191986258666

Since the decomposition is not unique, your function/program does not need to output the exact same results as these provided examples.

Very detailed rules

  1. Submissions should be in the form of a complete function or program. import statements do count towards the final score.

  2. You may assume the input A always contains at least a digit of 0, 3 or 7.

  3. You may assume a decomposition always exist.

  4. You may use BigInt if they are part of the standard libraries of the language, or can be installed through the language's de jure package manager.

  5. The function should be fast. It should take no more than 20 seconds to run on reasonably modern computer when fed a 100-digit number, and no more than 2 seconds when fed a 10-digit number.

  6. The function/program should support input up to at least 100 digits.

    • If the function/program can only support integers up to N<100 digits, there will be a penalty of +10×(100/N - 1) bytes to the final score. This is to encourage golfers to support a wider range of numbers even if importing may be verbose.
  7. There is no restriction on the presentation of input/outputs as long as they are clearly in decimal representation.

    • The function may input and output strings/BigInts if the built-in integer types are not sufficient.
    • The input may come from the function parameter, command line argument or STDIN.
    • The function may return the result, or just print the result directly to STDOUT.
    • However, signed overflow in the input/outputs are not allowed.
    • Approximate answers are not tolerated, the input/outputs must be exact.

Scoring

This is a . Shortest solution in bytes win.

There is a penalty if the program can only support numbers less than 100 digits:

  • 64-bit integers (19 digits) = +42 bytes
  • 63-bit integers (18 digits) = +45 bytes
  • 53-bit integers (15 digits) = +56 bytes
  • 31/32-bit integers (9 digits) = +101 bytes
\$\endgroup\$
  • 2
    \$\begingroup\$ Are you sure such decomposition is always possible? Can you sketch me a proof? \$\endgroup\$ – John Dvorak Nov 7 '14 at 10:28
  • \$\begingroup\$ Someone block 1, 5, 9 in the 95 Movie Quotes question then. \$\endgroup\$ – jimmy23013 Nov 7 '14 at 11:42
  • 3
    \$\begingroup\$ 100 digits? that means Python wins straight away, as it is the only commonly used language here that supports arbitrary precision integers. Why not 19 digits, which fits in a 64-but unsigned integer? (2^64= 18 446 744 073 709 551 616) \$\endgroup\$ – Level River St Nov 7 '14 at 12:38
  • 5
    \$\begingroup\$ @steveverrill Mathematica... GolfScript... CJam... \$\endgroup\$ – Martin Ender Nov 7 '14 at 14:26
  • 1
    \$\begingroup\$ And Java (had to say that) \$\endgroup\$ – Ypnypn Nov 7 '14 at 16:20
2
\$\begingroup\$

CJam, 70 bytes

ri:Q{;Qmr_Q^`1$`+730`&}g_Q^p

Try it online.

Randomly selects integers until it finds a match. This barely complies with the 20 second limit for 64-bit integers (using the Java interpreter), so I've added 42 to the actual byte count.

Example run

$ cjam t <<< 7777777777; echo
2695665494
6161166119
\$\endgroup\$
10
+150
\$\begingroup\$

Common Lisp, 240 224 183 173 169 bytes

Common Lisp is a bit verbose for golfing. However, this decomposes 100-digit numbers in under a second, and 200-digit integers in less than ten seconds, so no need for penalties. The algorithm is deterministic.

(defun s(z)(and #1=(some(lambda(q)(position q(format()"~a"z)))"037")(+ z(floor z(expt 10 #1#)))))
(defun d(x)(do((y x(or(s y)(s #3=(logxor x y))(return`(,y,#3#)))))(())))

The line feed between the functions is for typographic purposes only. Test run with the 100-digit reference input:

(time (d 5296080632396965608312971217160142474083606142654386510789497504098664630388377556711796340247136376))
took 677,000 microseconds (0.677000 seconds) to run.
      20,989 microseconds (0.020989 seconds, 3.10%) of which was spent in GC.
During that period, and with 8 available CPU cores,
     671,875 microseconds (0.671875 seconds) were spent in user mode
           0 microseconds (0.000000 seconds) were spent in system mode
 54,221,104 bytes of memory allocated.
(1864921261592819619661568919418981552559955289196969112566252282429216186594265918444566258544614425
 5891958562486995519825158818455999516899524658151445485616155916296966645869599949958954491929662561)

As a bonus, I'm including a version of the code that incrementally builds the solution top-down. It can manage a 1000-digit number in less than ten seconds, but cannot compete in golf due to the additional code.

(defun decompose (x)
  (flet ((s (z)
           (mapcan #'(lambda (c) (and #1=(position c #2=(format () "~a" z))
                                 (list (- (length #2#) #1# 1))))
                   '(#\0 #\3 #\7))))
    (do ((y x (let ((p (nconc (s y) (s #3=(logxor x y)))))
                (or p (return`(,y,#3#)))
                (+ y (expt 10 (apply #'max p))))))
        (nil))))

* (time (decompose (parse-integer (make-string 1000 :initial-element #\7))))
took 9,226,000 microseconds (9.226000 seconds) to run.
        90,966 microseconds (0.090966 seconds, 0.99%) of which was spent in GC.
During that period, and with 8 available CPU cores,
     9,234,375 microseconds (9.234375 seconds) were spent in user mode
             0 microseconds (0.000000 seconds) were spent in system mode
 487,434,560 bytes of memory allocated.
(8889898889152488921298888992819221914229899249999918899888899888888889999989141219898898888988988898888888888899142442899924898918898898988988895189988898888924192198992454114198911989191888889898888918888988988998888891421118891899122898888998989898888898988898888999988918888898889189918889888888899888989219188898998888988892119889198888988888894888912188898989952999888888888898899998988898889228918998949999998898898991141888898999988912121292118899889998989899999892889941898888911888898889118998898888911889889888891452888998889288921141888888942189888899988891918889118888888888989892198899199914111188988889421111188889118888918989988912989999998989891119888898888888892621229888988888999619888952462219889189899998899888889989898891118989218888888898962988891188899888888888999888888888888888888888891269188921288888888998898899214191188888888898992188998898889919888889989889899988892115549998888898889218899988998911898989199918898918988898888891889888989119899888889888998918889112189998
 4184469818464841952189561886965821566229261221619858498284264289194458622668559698924621446851546256444641488616184155821914881485164244662156846141894655485889656891849662551896595944656451462198891289692696856414192264846811616261884188919426294584158925218559295881946496911489245664261126565546419851585441144861859822815144162828551969425529258169849412525611662488849586554989254181228254465226521648916188265491499166186964881248156451994924294646681548996645996894665198811511522424996844864211629888924642289925565591484541149414914699289441561496451494562955652129199261462268846144518142486845251946444998812988291119592418684842524648484689261441456645518518812265495165189812912919529151991611962525419626921619824496626511954895189658691229655648659252448158451924925658586522262194585891859285841914968868466462442488528641466655911199816288496111884591648442984864269495264612518852292965985888414945855422266658614684922884216851481646226111486498155591649619266595911992489425412191)
* (apply #'logxor *)
7777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777
\$\endgroup\$
2
\$\begingroup\$

Python 2, 103 + 42 = 145 bytes

Python natively supports bigints, but this program far exceeds 20 seconds for a 100-digit number. However, it decomposes 64-bit integers in around 2 seconds.

from random import *
def d(a):
 b=c=0
 while set(`b`+`c`)&set('037'):
    b=randint(1,a);c=a^b
 return b,c
\$\endgroup\$
  • 1
    \$\begingroup\$ Clever idea using randomness. If you're defining a function, you don't need a while loop to keep trying random values -- you can just call the function again. Without need for control structure, you can then collapse the function to a lambda and a ternary: from random import* d=lambda a,b=0:set(`b`+`a^b`)&set(\'037\')and d(a,randint(1,a))or(b,a^b). Though you might be better off just not using a function. \$\endgroup\$ – xnor Nov 7 '14 at 20:40
  • \$\begingroup\$ I considered recursion, but it causes a stack overflow for large numbers (even just 11 digits). \$\endgroup\$ – Remy Nov 9 '14 at 1:36
1
\$\begingroup\$

Python 3 (132 bytes)

(This is just to stimulate better solutions. This is my solution when solving the original problem in ASCII movie.)

def d(a):
 l=len(str(a));s=int('1'*l);u=10**(l-1)
 while u:
  while set(str(s)+str((a^s)//u))&set('037'):s+=u
  u//=10
 print(s,a^s)

Although the behavior of bitwise xor in decimal system is pretty complicated, there is one major observation: modifying the low digits will not affect the high digits. Therefore, we can work top-down: try to make the top digits free of 0, 3, 7, and then work on the next digit, until the whole number is worked out. This allows us to run in linear time, then processing a thousand-digit number can complete under 1 second. (The Common Lisp solution is also using the same technique I believe.)

\$\endgroup\$
  • \$\begingroup\$ But fixing low digits may affect high digits. For instance, 997^8 == 1005. I think there is a kernel of an idea here, but it isn't obvious. \$\endgroup\$ – Keith Randall Nov 11 '14 at 17:33
  • \$\begingroup\$ @KeithRandall: Yes it is just like 999…999 + 1, but, given the choice of {1,2,4,5,6,8,9}, there would be some of them that won't affect the high digits. (e.g. 997^2 == 999). The inner while loop does the exhaustion to find the choice that keeps the high digits valid. \$\endgroup\$ – kennytm Nov 11 '14 at 17:37
  • \$\begingroup\$ right, but then it's not obvious (to me, at least) that there is definitely a digit that will work. \$\endgroup\$ – Keith Randall Nov 11 '14 at 17:38

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.