24
\$\begingroup\$

The problem statement here is pretty simple, take two real numbers on the range [0,1) as input and output their sum, with probability 1.

The catch here is that there are a lot of real numbers. There are in fact so many real numbers that it is impossible to fit all of them into any finite data type. As such, any way to input real numbers has to be potentially infinite, and any algorithm that handles arbitrary real numbers cannot consume all of the input.

For this challenge you will input (and output) real numbers as lazy sequence (e.g. stream, generator, lazy list, function) of bits, representing their binary expansion. You can assume that the input will be normalized and will not end in an infinite repetition of 1.

Even with this special input format it isn't possible to add any two real numbers. Any potential algorithm can be tricked into an infinite loop.

So instead we are going to settle for almost working. To "work" on a pair of inputs your program needs to be able to output any bit of the output in finite time. For example, if you output a generator I should be able to read to the 5th bit without the program getting stuck in a loop. Your answer needs to work with probability 1, meaning that the measure of the set of inputs which your program does work needs to have measure 1. The behavior for which the program doesn't work is undefined it can loop forever give an incorrect answer etc. so long as these cases themselves have measure zero.

This is the goal is to minimize the size of your source code as measured in bytes.

Examples

Here are some examples of rational numbers being added. You do not need to support any of these specific numbers.

1/3  = 0.01010101010101010...
+
1/5  = 0.00110011001100110...
=
8/15 = 0.10001000100010001...
3/8  = 0.011000000000000000...
+
3/16 = 0.001100000000000000...
=
9/16 = 0.100100000000000000...
17/95    = 0.001011011100111101111110101001110001001011011100111101111110101...
+
3/13     = 0.001110110001001110110001001110110001001110110001001110110001001...
=
506/1235 = 0.011010001110001100101111111000100010011010001110001100101111111...
\$\endgroup\$
15
  • 6
    \$\begingroup\$ I find the challenge description interesting & tantalizing, but difficult to concretely understand. Could you add an example to flesh-out "Any potential algorithm can be tricked into an infinite loop", for instance...? \$\endgroup\$ Apr 19 at 20:18
  • 1
    \$\begingroup\$ @DominicvanEssen Take for one input 0 followed by a random sequence S of 0s and 1s and 0 followed its complement S' for the other. The sum is 1,0,0,0, but your program will never have enough information to output the first 1. \$\endgroup\$
    – loopy walt
    Apr 19 at 20:25
  • 6
    \$\begingroup\$ @loopywalt It's a little more subtle, the sum is also 0,1,1,1... that is a valid output and the two are equal, however you can't output that either, because if at some point both inputs had a 1 in the same place it would cause a cascade that would fill out the 1s place. Basically to ever commit to a digit you need to find a place after it that has either a 0 in each or a 1 in each, but that's never true of S and S'. \$\endgroup\$
    – Wheat Wizard
    Apr 19 at 20:29
  • 3
    \$\begingroup\$ A non-random example of S and S' would be 1/3 and 2/3, which are compliments after the 1s place. \$\endgroup\$
    – Wheat Wizard
    Apr 19 at 20:30
  • 1
    \$\begingroup\$ Instead of two separate generator/stream inputs a and b, may we instead take a single generator/stream as input whose elements are a[0], b[0], a[1], b[1], ...? \$\endgroup\$ Apr 19 at 20:36

5 Answers 5

14
\$\begingroup\$

Python, 75 bytes

def f(*I,n=0):
 for a,b in zip(*I):yield from[a,*n*[1^a]][:-(n:=1+n*(a^b))]

Attempt This Online!

Takes two iterables and returns one.

How?

Count bits that differ between the inputs without outputting anything until an equal bit is encountered. Output this bit followed by counter times its complement. Reset counter and start over.

\$\endgroup\$
5
\$\begingroup\$

Rust, 222 199 bytes

|a:Box<dyn Iterator<Item=usize>>,b:Box<dyn Iterator<Item=usize>>|a.zip(b).scan(0,|z,(e,f)|Some(if e==f{let q=*z;*z=0;(e..=e).chain((1-e..2-e).cycle().take(q)).collect()}else{*z+=1;vec![]})).flatten()

Attempt This Online!

Just the type declaration of a iterator is already longer than some of the answers here :(

\$\endgroup\$
1
  • \$\begingroup\$ By moving the type declarations into the header you can save quite a few bytes: 139 bytes. \$\endgroup\$
    – JSorngard
    Apr 20 at 9:43
4
\$\begingroup\$

Javascript, 103 104 105 bytes

function*g(a){for(;;){for(i=0;(A=a.next().value)!=a.next().value;)i++;yield*[A,...Array(i).fill(+!A)]}}

More nicely formatted:

function*g(a){
    for(;;){
        for(i=0;(A=a.next().value)!=a.next().value;) i++;
        yield A;
        yield* Array(i).fill(+!A)
    }
}

Expects a generator function which yields the bits of the numbers to be added, interleaved.

\$\endgroup\$
4
  • 1
    \$\begingroup\$ You can use for(;;) instead of while(1) for -1 byte. \$\endgroup\$ Apr 19 at 21:02
  • \$\begingroup\$ Ah, of course, thanks! @ConorO'Brien \$\endgroup\$ Apr 19 at 21:06
  • \$\begingroup\$ I think you can save another byte by using a single yield: yield*[A,...Array(i).fill(+!A)] \$\endgroup\$ Apr 19 at 21:11
  • \$\begingroup\$ @ConorO'Brien, Yep, you're right. I had previously been yielding from another generator, and spread syntax doesn't seem to get values one at a time. (So it wasn't an option) \$\endgroup\$ Apr 19 at 21:18
4
\$\begingroup\$

Charcoal, 21 bytes

FN≔⁺NNθNηW⁻ηNNηI﹪⁺θη²

Try it online! Link is to verbose version of code. Takes input as n (1-indexed) and in interactive mode will prompt for interleaved input bits until it knows what value the nth output bit is but on TIO you just have to provide enough bits (if there aren't enough you'll see a prompt but the program will just halt). Explanation:

FN≔⁺NNθ

Input n pairs of bits but only keep the sum of the last pair.

NηW⁻ηNNη

Input further pairs of bits until two match.

I﹪⁺θη²

Add the matching bit to the sum from earlier and reduce modulo 2.

\$\endgroup\$
4
\$\begingroup\$

R, 62 60 bytes

Edit: -2 bytes thanks to pajonk

{t=0
\(x,y){u=t
t<<-`if`(x-y,t+1,0)
if(x==y)c(x,rep(!x,u))}}

Attempt This Online!

Port of loopy walt's Python approach.

Function that accepts sequential pairs of bits from the two numbers to be added as input to successive calls, and gives output when it can, otherwise outputs nothing. So the full output is the concatenated output of successive calls.
Input corresponds to the bits after the binary point, output begins with a single bit before the binary point, followed by all bits after the binary point (since we need to one more bit in case the two input numbers add-up to greater-than one).

Unfortunately my maths isn't good enough to determine when an infinite number of infinitely-small values sum to a finite value or to zero, so I'm blindly trusting that this approach is valid...

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Are the newlines before u=t and }} necessary? \$\endgroup\$
    – pajonk
    Apr 22 at 17:42
  • \$\begingroup\$ @pajonk - Of course not. What on earth was i thinking? Doh. Thanks. \$\endgroup\$ Apr 22 at 20:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.