Coding Games and Programming Challenges to Code Better
Send your feedback or ask for help here!
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
3 Likes
After writing a load of code and sweating I got through but I had no idea what BFS is.
The challenge was good but I would have wasted less time had I realised what I was getting into.
Definitely not for beginners like me.
I ran into the problem, that all tests went fine, but validation 5 failed.
A lot of searching and testing later I found that one edge case is missing in the tests.
My problem was that the last movie from the inputs, was in the solution chain before the last position. This caused a infinite loop in my programm at finding and processing the next movie in the chain after it.
I recoment to switch two movie input lines from the 3td or 5th test, so that the last input movie is at the second or third last position in the chain.
I thought the movie thing was a pretty good red herring. We can just treat each movie as a fully connected subgraph as we build up the full graph.