Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Can (x++ !== x) && (x++ === x); return true?

Tags:

javascript

A friend of mine come across this question at an interview

Find a value of x that will make this function return true

function f(x) {
    return (x++ !== x) && (x++ === x);
}

The interviewer added: x should be 5 characters max

I found multiple answers of 7 characters:

[["2**53-1"],["2*3**33"],["2-5**23"],["5**23-2"],["3**33*2"]]

But I couldn't find the one with 5 characters. (not even 6) . I was doubting that there is a solution that has 5 characters. But after research, I found this site: https://alf.nu/ReturnTrue that offers the same challenge and it turns out there is (are) solution(s) with 5 characters:

enter image description here

Can someone please help to know what is it?

like image 482
TSR Avatar asked Oct 12 '18 11:10

TSR


1 Answers

It is simple to do exhaustive search for solutions using different operations.

Since the only solutions that make f true are values >= than Number.MAX_SAFE_INTEGER, we immediately think of exponentiation or scientific notation to achieve them in a small space.


Exponentation

We use 2 characters, and we are left with only 3 for digits:

// n**mm
for (n = 0; n <= 9; ++n)
for (m = 0; m <= 99; ++m)
    if (f(n**m))
        console.log(n, m, n**m);

// nn**m
for (n = 0; n <= 99; ++n)
for (m = 0; m <= 9; ++m)
    if (f(n**m))
        console.log(n, m, n**m);

Since there are only 3 digits left, we cannot use an addition/subtraction here to offset things (it takes at least 2 characters).


Scientific notation

We use 1 character, so we are left with 4 potential digits:

// nEmmm
for (n = 0; n <= 9; ++n)
for (m = 0; m <= 999; ++m)
    if (f(n*(10**m)))
        console.log(n, m, n*(10**m));

// nnEmm
for (n = 0; n <= 99; ++n)
for (m = 0; m <= 99; ++m)
    if (f(n*(10**m)))
        console.log(n, m, n*(10**m));

// nnnEm
for (n = 0; n <= 999; ++n)
for (m = 0; m <= 9; ++m)
    if (f(n*(10**m)))
        console.log(n, m, n*(10**m));

However, in this case we can do addition/subtraction:

// nEm+d
for (n = 0; n <= 9; ++n)
for (m = 0; m <= 9; ++m)
for (d = 0; d <= 9; ++d)
    if (f(n*(10**m)+d))
        console.log(n, m, d, n*(10**m)+d);

// nEm-d
for (n = 0; n <= 9; ++n)
for (m = 0; m <= 9; ++m)
for (d = 0; d <= 9; ++d)
    if (f(n*(10**m)-d))
        console.log(n, m, d, n*(10**m)-d);

Full expression search

We can also do a full exhaustive search over the entire string space considering that it is only 5 characters.

To speed it up a bit, let's only use characters that we think can actually get us there (e.g. the digits, the arithmetic operators, etc). If we use 24 characters like below, that is 24**5 possibilities, which is only a few millions to test (it should take only a minute or so in a modern computer):

const s = [
    "0","1","2","3","4","5","6","7","8","9",
    "e",".",
    "*","+","-","/","%",
    "!","^","&","|","<",">","~"
];
const l = s.length;
for (var n1 = 0; n1 < l; ++n1)
for (var n2 = 0; n2 < l; ++n2)
for (var n3 = 0; n3 < l; ++n3)
for (var n4 = 0; n4 < l; ++n4)
for (var n5 = 0; n5 < l; ++n5)
    try {
        const expr = s[n1] + s[n2] + s[n3] + s[n4] + s[n5];
        if (f(eval(expr)))
            console.log(expr);
    } catch (e) {};

Note: we have to use try...catch, since many of the expressions will be invalid. Also, be careful with the variable names you use (e.g. if you use e as a loop counter, you will get strings like --e which will get you into an infinite loop!

like image 75
Acorn Avatar answered Nov 15 '22 14:11

Acorn