We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
- Prepare
- Algorithms
- Graph Theory
- Frog in Maze
- Discussions
Frog in Maze
Frog in Maze
Sort by
recency
|
39 Discussions
|
Please Login in order to post a comment
I used markov chains. It can pass 46/47 of the test cases. Can't do the 5th test case because of the time limit.
5th test case n*m*25 markov chains = 0,462033 5th test case n*m*70 markov chains = 0,462102
but the second one takes too much time. n*m*25 is enough for the other test cases.
I don't think the code would be able to do it fast enough even if I change all of the lists to arrays (first did all of the code using arraylists than afterwards changed only the matrices multiplying part to arrays to make it faster) and then destroy the redundant methods. Probably needs a faster way to multiply matrices.
Here is my solution in java7, java8, C++ HackerRank Frog in Maze Problem Solution
Here is the solution of Frog in Maze Click Here
Im so close. How does test case #2 come out to 50% chance? there are zero tunnels. My logic is so close, but I would think the below test case would be .25 * .25 * .50 = 0.325 to reach the exit. What am I assuming?
*- Input (stdin) *- 3 7 0 *- ##OOO## - %OOAOO *- ##OOO##
Expected Output 0.5000000000
You land at the regional airport in time for your next flight. In fact, it looks like you'll even have time to grab some food: all flights are currently delayed due to issues in luggage processing. Due to recent aviation regulations, many rules (your puzzle input) are being enforced about bags and their contents; bags must be color-coded and must contain specific quantities of other color-coded bags. Apparently, nobody responsible for these regulations considered how long they would take to enforce!
For example, consider the following rules:
light red bags contain 1 bright white bag, 2 muted yellow bags.
dark orange bags contain 3 bright white bags, 4 muted yellow bags.
bright white bags contain 1 shiny gold bag.
muted yellow bags contain 2 shiny gold bags, 9 faded blue bags.
shiny gold bags contain 1 dark olive bag, 2 vibrant plum bags.
dark olive bags contain 3 faded blue bags, 4 dotted black bags.
vibrant plum bags contain 5 faded blue bags, 6 dotted black bags.
faded blue bags contain no other bags.
dotted black bags contain no other bags.
These rules specify the required contents for 9 bag types. In this example, every faded blue bag is empty, every vibrant plum bag contains 11 bags (5 faded blue and 6 dotted black), and so on.
You have a shiny gold bag. If you wanted to carry it in at least one other bag, how many different bag colors would be valid for the outermost bag? (In other words: how many colors can, eventually, contain at least one shiny gold bag?)
In the above rules, the following options would be available to you:
A bright white bag, which can hold your shiny gold bag directly.
A muted yellow bag, which can hold your shiny gold bag directly, plus some other bags.
A dark orange bag, which can hold bright white and muted yellow bags, either of which could then hold your shiny gold bag.
A light red bag, which can hold bright white and muted yellow bags, either of which could then hold your shiny gold bag.
So, in this example, the number of bag colors that can eventually contain at least one shiny gold bag is 4.
How many bag colors can eventually contain at least one shiny gold bag? (The list of rules is quite long; make sure you get all of it.
Input Format
light red bags contain 1 bright white bag, 2 muted yellow bags.
dark orange bags contain 3 bright white bags, 4 muted yellow bags.
bright white bags contain 1 shiny gold bag.
muted yellow bags contain 2 shiny gold bags, 9 faded blue bags.
shiny gold bags contain 1 dark olive bag, 2 vibrant plum bags.
dark olive bags contain 3 faded blue bags, 4 dotted black bags.
vibrant plum bags contain 5 faded blue bags, 6 dotted black bags.
faded blue bags contain no other bags.
dotted black bags contain no other bags.
Constraints
bag type1 contain m bag type2, n bag type 3 ... where n is >1
Output Format
1<=COUNT