[Community Puzzle] Six Degrees of Kevin Bacon - Puzzle discussion

Coding Games and Programming Challenges to Code Better

Created by @StepBack13,validated by @jddingemanse,@kayou and @Syrihus.
If you have any issues, feel free to ping them.

The puzzle is OK, my only concern is that it is too similar to the already existing Erdős number puzzle

On a sidenote: Erdős-Bacon number is funnier than any of these numbers and it is also harder for anyone to get a finite value. My son has <= 8.

2 Likes

I found that the last test fails as it says the answer is four while my solution says it is three. I tried writing it down on paper and it seems like three is correct.
The final validation passed 100 % so it might be the test case that is wrong. Perhaps it is finding the first Bacon number that is less than some large number?

Could you please show your details of “three” like the example in the statement?

We start at movie number 6 (index 5) with actors:

Anusha Viswanathan, Rahul Dev Bose, Kheyali Dastidar, Priyanka Bhattacharjee (Bacon number 0)

Kheyali Dastidar is in movie 11 (index 10) with actors:

Utpal Dutt, Soumitra Chatterjee, Ruma Guha Thakurta, Satya Bandopadhyay, Kheyali Dastidar (Bacon number 1)

Utpal Dutt is in movie 3 (index 2) with actors:

Hugh Grant, Shabana Azmi, Supriya Pathak, John Hurt, Soumitra Chatterjee, Utpal Dutt (Bacon number 2)

John Hurt is in movie 22 (index 21) with actors:

Kevin Bacon, Tippi Hedren, Shawnee Smith, Ray Stevenson, John Hurt (Bacon number 3)

We end up with the bacon number: 3

Anusha Viswanathan → Kheyali Dastidar → Utpal Dutt → John Hurt → Kevin Bacon
4 arrows = 4 degrees of separation = bacon number is 4.

1 Like

Nice puzzle to get a grasp of graphs, that could contain circular references.
Thank you.

I would love to see the output of the validators, because I calculated the Bacon Number for the whole set of actors and just would like to know, how long it took.

You are absolutely correct. I must review my code. Thank you for making the final step clear to me.

2 Likes

What is more interesting, is that if I understand you correctly, your code passed all Validators, despite this problem at one of the tests .

1 Like

I have tested my original program again. Today all tests succeeded.

I tested this, and didn’t optimize it - it calculates all possibilities - all paths - and I still got 100%.
Perhaps you need a MUCH larger dataset?? or I did I do something wrong?

Is your question ‘I got 100%, did I do something wrong?’?

If you are surprised that no optimization is needed: it is a contribution classified as Easy, so it is valid to let the challenge only be about correctly checking all possibilities, and not necessarily about optimization.

I’d like to add that if it was about optimization, a lot of beginners would be crying here because the puzzle should be Medium or Hard.

If you are interested in optimizing your pathfinding, there are a lot of other puzzles here :
https://www.codingame.com/learn/BFS
https://www.codingame.com/learn/pathfinding
(some of those - but not all - will need to optimize your pathfinding)

__
EDIT : For example this one will timeout if you check all pathes : 11-puzzle

2 Likes