DEV Community

loading...

The easiest problem you cannot solve.

JavaScript Joel
Cofounded Host Collective (DiscountASP.net). Cofounded Player Axis (Social Gaming). Computer Scientist and Technology Evangelist with 20+ years of experience with JavaScript!
・1 min read

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=

Cheers!

Discussion (43)

Collapse
entrptaher profile image
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))()()
Collapse
joelnet profile image
JavaScript Joel Author
K(K)()(dog)()
K(K(K)()(dog))(K)()
K(K(K)(cat)(dog))()()

Very creative!

Collapse
theodesp profile image
Theofanis Despoudis

"cat and dog must appear exactly once."

That violates

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

Collapse
joelnet profile image
JavaScript Joel Author

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

Collapse
entrptaher profile image
Md. Abu Taher 👨‍💻

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

Collapse
joelnet profile image
JavaScript Joel Author

There is no restriction to call K, right?

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

Collapse
joelnet profile image
JavaScript Joel Author

Minions clapping and screaming

I assumed the other solution would have been found first.

Congratulations!

Collapse
entrptaher profile image
Md. Abu Taher 👨‍💻

Well I updated with other solution.

Thread Thread
joelnet profile image
JavaScript Joel Author

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 ;)

Thread Thread
entrptaher profile image
Md. Abu Taher 👨‍💻

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

Thread Thread
joelnet profile image
JavaScript Joel Author

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

Collapse
kspeakman profile image
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"
Collapse
joelnet profile image
JavaScript Joel Author

I did not consider this as a possible solution!

GIF of Simon Cowell exclaiming "Brilliant"

Collapse
ajnasz profile image
Lajos Koszti
K(cat && dog)()

?

Collapse
entrptaher profile image
Md. Abu Taher 👨‍💻

Brilliant.

Collapse
joelnet profile image
JavaScript Joel Author

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

Collapse
en0 profile image
Ian Laird • Edited

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}`)()
Collapse
joelnet profile image
JavaScript Joel Author

Beautiful!

Collapse
kip13 profile image
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'
Collapse
joelnet profile image
JavaScript Joel Author

Congratulations

So many unique solutions. Fantastic!

Collapse
themindfuldev profile image
Tiago Romero Garcia • Edited

These are less clever yet might be valid solutions:

K('')(cat)+K(dog)()
K()(cat);K(dog)()
Collapse
joelnet profile image
JavaScript Joel Author

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

Collapse
themindfuldev profile image
Tiago Romero Garcia

One more:

K([cat,dog])()[1];
Collapse
joelnet profile image
JavaScript Joel Author • 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.

Collapse
jrista profile image
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

Collapse
joelnet profile image
JavaScript Joel Author

After you research SKI Combinators, look into Church Encoding.

Collapse
theoutlander profile image
Nick Karnik

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

K.call(1,2)()
Collapse
joelnet profile image
JavaScript Joel Author

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

Collapse
jochemstoel profile image
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. :)

Collapse
joelnet profile image
JavaScript Joel Author

But cats and dogs are the best ;)

Collapse
handsomeone profile image
Zhou Qi

Comma operator:

K((cat, dog))()
Collapse
joelnet profile image
JavaScript Joel Author

Extra hearts for the comma operator. Kudos!

Collapse
metalbrain28 profile image
metalbrain28

Well...

K((function *() { yield(arguments); }))(cat)(dog).next().value[0];
Collapse
joelnet profile image
JavaScript Joel Author

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

joelnet profile image
JavaScript Joel Author • 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!

Collapse
vonheikemen profile image
Heiker

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

K.bind(null, [cat, dog].pop())()()
Collapse
joelnet profile image
JavaScript Joel Author

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

Very creative!

Collapse
motss profile image
Rong Sen Ng

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

Collapse
joelnet profile image
JavaScript Joel Author

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

Collapse
joelnet profile image
JavaScript Joel Author

Awesome work!

You found the clue I left, the K combinator! And it does come from the SKI calculus.

So many interesting solutions!