Problem 675483 · medium · Level 06 Heuristics & Optimization

How a Train of Wagons Rings

eigenvalues · modes · state space · coupled oscillators · numpy · poles

A short goods train is a row of wagons joined by couplings that act like a spring with a damper beside it. When the locomotive jerks, the wagons surge back and forth against each other. A simulator for wagons 0, 1, ..., n-1 (masses masses[j] in kg; coupling i joins wagon i to wagon i + 1, with stiffness springs[i] in N/m and damping dampers[i] in N·s/m) uses the state

s = [p0, p1, ..., p(n-1), v0, v1, ..., v(n-1)]       (positions in m, then speeds in m/s)

and moves it on by dt seconds like this:

F = [0] * n
for each coupling i:   f = springs[i] * (p[i+1] - p[i]) + dampers[i] * (v[i+1] - v[i])
                       F[i] += f;  F[i+1] -= f
new v[j] = v[j] + dt * F[j] / masses[j]          for every wagon
new p[j] = p[j] + dt * (new v[j])                for every wagon (using the new speed)

Every line is linear in the state, so one step is s[k+1] = A s[k] for a 2n by 2n matrix A. You do not need to work A out on paper: column j of A is where the unit state e_j (1 in place j, 0 elsewhere) goes in one step, so stepping each of the 2n unit states gives all its columns.

The eigenvalues of A are the train's modes (the poles of any output you might measure). An eigenvalue z = r * e^(jθ) with angle θ > 0 is a mode that rings at θ / (2π dt) hertz and keeps the share r of its swing each step. (Its conjugate, at -θ, is the same mode; real eigenvalues do not ring, and the train rolling along as one body gives eigenvalues at 1.)

Write wagon_modes(masses, springs, dampers, dt) that returns the list of pairs (frequency_hz, r), one for every eigenvalue with angle θ > 1e-6 (angle from math.atan2(z.imag, z.real)), sorted by frequency.

Examples

Input:  masses = [1000, 1000], springs = [40000], dampers = [0], dt = 0.01
Output: [(1.4240000227632286, 0.9999999999999994)]
Explanation: two 1-tonne wagons bounce against each other at 1.42 Hz (sqrt(k (1/m0 + 1/m1)) / 2π
= 1.4235 Hz for the real, continuous train); with no damping the swing never shrinks.

Input:  masses = [1000, 2000, 1000], springs = [40000, 40000], dampers = [500, 500], dt = 0.01
Output: [(1.0072248312959498, 0.997496867163), (1.4253397524390115, 0.9949874371066211)]
Explanation: two ways to ring: the end wagons swinging against each other around a still middle
one (1.01 Hz), and the middle wagon against both ends (1.43 Hz), which damps faster.

Input:  masses = [1000, 1000], springs = [40000], dampers = [20000], dt = 0.01
Output: []
Explanation: so much damping that the wagons creep together without ringing.

Constraints

  • 1 <= n <= 6; len(springs) == len(dampers) == n - 1; masses and springs positive, dampers at least 0
  • dt is small enough that every mode turns by much less than half a circle per step
  • answers are compared with a tolerance of 1e-6; tuples or lists are accepted for the pairs

Goals

  • Turn a stated update rule into its state matrix A by stepping each unit state vector
  • Find the system's modes as the eigenvalues of A
  • Read each oscillating mode's frequency in hertz and its decay per step from its eigenvalue
Starting Python…