JavaScript Joel

Posted on

# The easiest problem you cannot solve.

Given the following code:

const K = a => b => a
const cat = 'cat'
const dog = 'dog'

Calling K like this will output cat

K(cat)(dog)
//=> "cat"

How can you call K to output dog without swapping the order of cat and dog?

cat and dog must appear exactly once.

The Given cannot be modified.

// INVALID: Cannot swap order!
K(dog)(cat)

// NO CHEATING: May only appear once.
K.bind(null, dog)(cat)(dog)

I know of two ways to solve this problem. Surprise me with another!

I should have also specified no bind, call, or apply, but the solutions are just too interesting :)

Hints: K in the problem is the K combinator, part of the SKI combinator calculus.

Spoilers are in the comments! BEWARE!

Many great solutions have been posted below! A lot I never considered. Also some very creative loopholes around the rules I created ;)

Here's one solution that went undiscovered. It's base64 encoded to hide the "spoiler". But if you are curious you can decode it using your console's atob function.

Syh4PT54KShjYXQpKGRvZyk=

## Top comments (40)

Md Abu Taher • Edited

There is no restriction to call K, right?

K(K)(cat)(dog)()
K(dog)()

Done! Both of these should output dog.

Update: You can actually put anything you want instead of cat. Or complicate it even more with infinite recursive inputs.

K(K)()(dog)()
K(K(K)()(dog))(K)()
K(K(K)(cat)(dog))()()

Theofanis Despoudis

"cat and dog must appear exactly once."

That violates

K(dog)()
K(K)()(dog)()
K(K(K)()(dog))(K)()

JavaScript Joel

I added that rule in afterwards. These solutions were valid at the time he posted, so I'll give him credit for the creativity :)

Md Abu Taher

I was the first to solve his problem :D
He changed the rules after I posted my solution.

JavaScript Joel

There is no restriction to call K, right?

There is also a solution with a single call to K :)

JavaScript Joel
K(K)()(dog)()
K(K(K)()(dog))(K)()
K(K(K)(cat)(dog))()()

Very creative!

JavaScript Joel

I assumed the other solution would have been found first.

Congratulations!

Md Abu Taher

Well I updated with other solution.

JavaScript Joel

haha I didn't consider K(dog)() would be within the rules. I have updated to rules to require both dog and cat to appear exactly once ;)

Md Abu Taher

Lol no! You cannot change the rules after I won :P

JavaScript Joel

I'm still giving you credit for both solutions ;)

Kasey Speakman • Edited

In FP, there is a fairly common operation for this called flip. Here is a solution I tested in Chrome console.

const flip = f => a => b => f(b)(a)
flip(K)(cat)(dog)
// "dog"

JavaScript Joel

I did not consider this as a possible solution!

Lajos Koszti
K(cat && dog)()

?

Md Abu Taher

Brilliant.

JavaScript Joel

Technically within the rules and as valid as any other solution!

I didn't see this one in the comments

K(cat && dog)();
K()(cat)||dog;

And arrays are fun

K.call(null, [cat, dog].reverse()[0])();
K.apply(null, [cat, dog].reverse())();
K([ ...cat, ...dog].slice(3).join(""))();

Technically i think this follows the rules.

K({ cat: dog })()

And if the does then this should work too

K(`\${cat} \${dog}`)()

JavaScript Joel

Beautiful!

kip • Edited
> K.call(null, (cat, dog))()
'dog'

> K.apply(null, [cat, dog].reverse())()
'dog'
> (cat, K(dog))()
'dog'
> K(((...args) => args[1])(cat, dog))()
'dog'

JavaScript Joel

So many unique solutions. Fantastic!

Jon

Well, I looked up SKI combinators. If I am understanding it correctly, and if I've implemented S correctly here...I think the following would work:

const S = x => y => z => x(z)(y(z));
S(K)(K(cat))(dog);

I am going to have to add "Learn SKI Combinators" to my list of things to do. :D

JavaScript Joel

After you research SKI Combinators, look into Church Encoding.

Tiago Romero Garcia • Edited

These are less clever yet might be valid solutions:

K('')(cat)+K(dog)()
K()(cat);K(dog)()

JavaScript Joel

lol. Clearly I have to get better at writing rules! Technically these qualify!

Tiago Romero Garcia

One more:

K([cat,dog])()[1];

JavaScript Joel • Edited
eval(K.toString().replace('b', 'a'))(cat)(dog)

This one is pretty creative. Modifying the original K function to swap a and b. I like it.

Jochem Stoel

Hey Joel, I enjoy your articles and I think you deliver a good contribution overall to this website but I would like to see you use better use cases in your examples than cats and dogs meowing. Not for me but for others less experienced. :)

JavaScript Joel

But cats and dogs are the best ;)

Nick Karnik

This call makes no sense in reality, but it will yield the desired output:

K.call(1,2)()

JavaScript Joel

Pretty interesting solution. You are binding the first value to this so that the a gets set as your second argument. Very creative!

metalbrain28

Well...

K((function *() { yield(arguments); }))(cat)(dog).next().value[0];

JavaScript Joel

Generators and iterators. quite a unique solution. I love it!

Zhou Qi

Comma operator:

K((cat, dog))()

JavaScript Joel

Extra hearts for the comma operator. Kudos!

JavaScript Joel • Edited

Exactly! That is definitely the I combinator. It works beautifuly with the K combinator in the problem to solve this problem.

Two parts of SKI combinator calculus!

Rong Sen Ng

Do you really need the second dog since you already .bind?

JavaScript Joel

Maybe I do not understand, what is the second dog?

Heiker

I give up. This is still within the rules, right?

K.bind(null, [cat, dog].pop())()()

JavaScript Joel

lol. not what I was looking for, but I would say it technically meets the rules.

Very creative!