# Diffing "some chords" and "Some say that he constructed the bridge on the river Kwai"

 Title: some chords Some say that he constructed the bridge on the river Kwai Author: Cameron Nowzari Magnus S Submitted: 2010-11-17 08:08:05 UTC 2010-11-17 08:56:55 UTC Status: Passed Passed Score: 815.654 815.739 Result: 4045 (cyc: 9, node: 1884) 4045 (cyc: 9, node: 1876) CPU Time: 67.844 68.056 Code: ```function [thrustRow, thrustCol] = npp(chart, aIndex, bIndex, maxThrottle) [thrustRow, thrustCol,score] = nickelfelpeter(chart, aIndex, bIndex, maxThrottle); if score<21 return; return; else [thrustRow1, thrustCol1,score1] = zeemcv(chart, aIndex, bIndex, maxThrottle); if score1 < score thrustCol = thrustCol1; thrustRow = thrustRow1; end end end function [thrustRow, thrustCol, score] = nickelfelpeter(chart, aIndex, bIndex, maxThrottle) ONEHUNDRED = 100; rand(1,14); y_winds = chart(:,:,1); x_winds = chart(:,:,2); [ny,nx] = size(x_winds); ay = rem(aIndex-1, ny) + 1; ax = (aIndex - ay)/ny + 1; by = rem(bIndex-1, ny) + 1; bx = (bIndex - by)/ny + 1; X = repmat(1:nx, ny,1); Y = repmat((1:ny)', 1,nx); dist_to_B = ((X - bx).^2 + (Y - by).^2).^1.15; dist_to_A = ((X - ax).^2 + (Y - ay).^2).^1.155; dist_to_B_w = dist_to_B*1e-4; dist_to_A_w = dist_to_A*1e-4; xvel = 0*x_winds; fuel = xvel+ONEHUNDRED; fuel(aIndex) = 0; yvel = xvel; checked = xvel; previous_stop = xvel; min_fuel = 0; cost_to_B = dist_to_B(aIndex); zoon = nx*ny*[10 0.37]; ziter = [500 700] .* (1-0.05*rand(1,2)); sf = [0.31 0.19]; for i = 1:2 SDB_tf = dist_to_B(:)<=zoon(i); SDB_idx = find(SDB_tf); SDBchecked = checked(SDB_tf); SDBfuel = fuel(SDB_tf); SDBdist_to_B_w = dist_to_B_w(SDB_tf); SDBdist_to_B = dist_to_B(SDB_tf); SDBxvel = xvel(SDB_tf); SDByvel = yvel(SDB_tf); SDBX = X(SDB_tf); SDBY = Y(SDB_tf); SDBprevious_stop = previous_stop(SDB_tf); slowdown = maxThrottle+SDBdist_to_B*sf(i); it = 0; metrix = SDBfuel + SDBchecked + SDBdist_to_B_w; while ( min_fuel <= cost_to_B && ~all(SDBchecked) && it < ziter(i)) it = it + 1; [dummy,i_p] = min(metrix); i_p_full = SDB_idx(i_p); min_fuel = SDBfuel(i_p); i_y = rem(i_p_full - 1,ny) + 1; i_x = (i_p_full - i_y)/ny + 1; i_y_winds = y_winds(i_p_full); i_x_winds = x_winds(i_p_full); i_vy = SDByvel(i_p) + i_y_winds; i_vx = SDBxvel(i_p) + i_x_winds; i_new_vy = SDBY - i_y; i_new_vx = SDBX - i_x; i_thrust = abs(i_new_vx - i_vx) + abs(i_new_vy - i_vy); i_fuel = i_thrust + min_fuel; i_impr_tf = (i_thrust <= maxThrottle) & (abs(i_new_vy+i_y_winds)+abs(i_new_vx+i_x_winds)1) zp = Z - target; totalT = abs(real(zp)) + abs(imag(zp)); boxp = totalT <=maxThrottle; % & rowT<=maxThrottle & ~checked; new_fuel = totalT + min_fuel; update = boxp & new_fuel < fuel; T = zwind(update) + (tvz-target); % zp + tvz + winds; update(update) = abs(real(T)) + abs(imag(T)) < md2B(update); fuel(update) = new_fuel(update); previous_stop(update) = p; [~,p] = min(fuel + checked); min_fuel = fuel(p); bestz = Z(p); z = Z(previous_stop(p)); tvz = bestz - z; target = bestz + tvz + winds(p); checked(p) = INF; end fuel = fuel + dist_to_B; [~,p] = min(fuel); checked = fract_d2A; checked(p) = Inf; return_previous_stop = zeros(ny*nx,1); target = 2*Z(p)-Z(previous_stop(p))+winds(p); min_fuel = fuel(p); while ~any(checked(zoonA)>1) zp = Z - target; totalT = abs(real(zp)) + abs(imag(zp)); boxp = totalT <=maxThrottle; boxp = totalT <=maxThrottle; new_fuel = totalT + min_fuel; update = boxp & new_fuel < fuel; fuel(update) = new_fuel(update); return_previous_stop(update) = p; [~,p] = min(fuel + checked); min_fuel = fuel(p); bestz = Z(p); if ~return_previous_stop(p) z = Z(previous_stop(p)); else z = Z(return_previous_stop(p)); end target = 2*bestz -z + winds(p); checked(p) = INF; end [score,p] = min(fuel+dist_to_A); tra=[ny, nx]*0; % tra=previous_stop'*0; k=0; turned=false; while p k=k+1; tra(k)=p; Z(k)=p; if turned||~return_previous_stop(p) turned=true; p=previous_stop(p); else p=return_previous_stop(p); end end tra=tra(k:-1:1); trar = rem(tra-1, ny) + 1; trac = (tra - trar)/ny + 1; Z=Z(k:-1:1); trar = rem(Z-1, ny) + 1; trac = (Z - trar)/ny + 1; accelr=diff([0 diff(trar)]); accelc=diff([0 diff(trac)]); accelr=diff([0;diff(trar)]); accelc=diff([0;diff(trac)]); if numel(tra)<2 if numel(Z)<2 thrustRow=[]; thrustCol=thrustRow; else w = winds(tra(1:end-1)).'; w = winds(Z(1:end-1)); thrustRow = accelr-imag(w); thrustCol = accelc-real(w); end end```