There appears to be no difference between the 2 APPs. So how come Uber's patent didn't prevent Lyft from stealing its ideas?
This answer is my own speculation and interpretation, not based on any inside knowledge at Lyft nor from any litigation. Patents are only as good as their claims, especially their independent claims. In PDF of Uber's main-business-model patent, the claims 1 and 15 are the 2 independent claims that Lyft could conceivably infringe solely based on having an analogous business model. Claims (especially independent claims that are not dependent claims deriving from an independent claim) can be bypassed by doing the same or similar outcome differently. Unless explicit using an “or” conjunction, the various clauses in an independent claim default to being “and” conjuncted. This means that if a(n Uber-assigned) patent stakes its claim by describing A-and-B-and-C-and-D, then a competitor(-assigned Lyft) patent or lack thereof could bypass the entire independent claim by figuring out a devious way to accomplish much the same outcome but by using A-and-X-and-C-and-Y without using B itself or D itself, as long as X is not isomorphic to B and Y is not isomorphic to D.
Given the sweeping breadth that Uber's claims 1 and 15 describe their core consumer ride-pick-up business model (which seems to at 1st surface-level glance be the same business model as Lyft) in Uber's '512 patent, it would at first seem difficult for Lyft to be able to bypass the accumulation of “and”-conjuncted clauses in claims 1 and 15 in Uber's '512 patent. But for hypothetical devil's advocacy, let us delve into what might be the weaker portions of the “and”-conjuncted clauses in claims 1 and 15. The “in response to receiving the triggered transmission of the transport request” limitation that precedes “initiating [programmatically, without human intervention] the selection process by programmatically selecting an available vehicle from the one or more vehicles assigned to transport the customer” a competitor (hypothetically Lyft) would have room in just this one clause to bypass the entire patent by (instead of programmatically having corporate servers automatedly pick a driver) sending out bid requests to the potential drivers to force the human-user drivers to place a bid in an auction of sorts to see which driver wanted that customer-pick-up badly enough, even if that driver was not quite optimal in distance or time (and thus would have not been the selected driver in Uber's '512 patent). As witnessed by this hypothetical example here, by surgically replacing just one step in the method that is the heart of '512 patent's claims 1 and 15, the chain of “and” clauses is broken by not being a match, and those claims are bypassed, hence bypassing the entire patent by replacing the 100% automated selection of driver with a human-based bidding at auction among the drivers.
Again for hypothetical devil's advocacy, the a-posteriori “in response” could be another weak link in the “and”-clause chain of claims 1 and 15, where a Lyft-eqsue competitor could simply precompute a priori the driver selection (based on certain constraints/mathematical-formula) in a vicinity prior to the customer-to-be-picked-up requesting a ride; in my auction business model, the driver's could conduct an auction minutes ahead of time for who wants forthcoming customer-to-be-picked-up-within-this-vicinity badly enough, minutes prior to the customer ever having an inkling that they wish to open their customer-end app to request a ride.
I am not saying that Lyft actually conducts such bidding auctions among drivers; I am merely pointing out how a clever Lyft engineer and/or lawyer could find just one weak link in Uber's '512 patent's chain of “and” clauses to bypass both of the independent clauses, thus bypassing all of the dependent clauses too, thus bypassing the entire patent. Any different-enough substitution of any weak link in the “and”-clause chain in each independent clause is enough to bypass the at-first-seemingly-onerous entire chain of staked-claim meaning's metes & bounds.