DEV Community πŸ‘©β€πŸ’»πŸ‘¨β€πŸ’»

DEV Community πŸ‘©β€πŸ’»πŸ‘¨β€πŸ’» is a community of 966,904 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

Create account Log in
JavaScript Joel
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=

Cheers!

Top comments (43)

Collapse
 
entrptaher profile image
Md. Abu Taher πŸ‘¨β€πŸ’» • Edited on

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 on

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 on

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 on
> 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 on

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 on
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 on

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?

Need a better mental model for async/await?

Check out this classic DEV post on the subject.

β­οΈπŸŽ€ JavaScript Visualized: Promises & Async/Await

async await