Skip to content

Instantly share code, notes, and snippets.

@itzbernoulli

itzbernoulli/code.rb

Created May 31, 2020 00:07
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save itzbernoulli/3c2900de587ea80ce943aff0cbe2caf3 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save itzbernoulli/3c2900de587ea80ce943aff0cbe2caf3 to your computer and use it in GitHub Desktop.
Download ZIP
Racing Car (hackerrank)
Raw
code.rb
class Node
attr_reader :value
attr_accessor :right, :left
def initialize(value)
@value = value
@left =nil
@right =nil
end
end
def choice(n)
if n == 1
return 2,3
elsif n == 2
return 1,3
else
return 1,2
end
end
def pushNode(node,first,second)
if node.left
pushNode(node.left,first,second)
else
node.left = Node.new(second)
end
if node.right
pushNode(node.right, first,second)
else
node.right = Node.new(first)
end
end
def traverse(node)
if node == nil
return
end
if node.left
traverse(node.left)
end
if node.right
traverse(node.right)
end
end
def minimumMovement(obstacleLanes)
# Write your code here
arr = Array.new
obstacleLanes.each do |lane|
arr << choice(lane)
end
root = Node.new(2);
arr.each do |inner|
pushNode(root, inner[0], inner[1])
end
traverse(root)
end
minimumMovement([2,1,2])
# minimumMovement([2,1,3,2])
@at-tyagi
Copy link

at-tyagi commented Oct 18, 2024 •
edited
Loading 

unordered_map<string,int> dp;
unsigned int recur(int i, int curr_lane,unsigned int steps, vector<vector<int>> &lane)
{
      string key=to_string(curr_lane)+"|"+to_string(i);
      if(lane[curr_lane][i]==1) return INT_MAX;
      if(i==lane[0].size()) return steps;
      if(dp.find(key)!=dp.end()) return dp[key]+steps;
      unsigned int ans=INT_MAX;
      for(int k=0;k<3;k++)
          if(curr_lane==k)
              ans=min(ans,recur(i+1,k,steps,lane));
          else
              ans=min(ans,recur(i+1,k,steps+1,lane));
      dp[key]=ans-steps;
      return ans;
}

unsigned int fun(vector<vector<int>> &lane, int curr_lane)
{
      unsigned int ans=recur(0,curr_lane,0,lane);
      if(ans>=INT_MAX) return -1;
      return ans;
}

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment