A318271 The optimum crossing time for the Bridge and Torch problem, given that the crossing times for the group's members are given by the n-th partition in A026791.
1, 1, 2, 3, 2, 3, 5, 4, 3, 2, 4, 7, 6, 5, 5, 4, 3, 5, 9, 8, 7, 6, 6, 6, 5, 6, 4, 3, 6, 11, 10, 9, 8, 8, 7, 7, 8, 7, 7, 6, 7, 5, 4, 7, 13, 12, 11, 10, 10, 9, 9, 9, 8, 7, 8, 9, 8, 8, 7, 10, 8, 8, 6, 5, 4, 8, 15, 14, 13, 12, 12, 11, 11, 11, 10, 9, 10, 10, 9, 8, 9
Offset: 1
Examples
When the crossing times are [1,2,5,10], the minimum total time for the group to cross is 17 minutes: (2m) 1 and 2 cross, (1m) 1 returns, (10m) 5 and 10 cross, (2m) 2 returns, (2m) 1 and 2 cross. +----+--------------------+------+ | n | Crossing times | a(n) | +----+--------------------+------+ | 1 | [1] | 1 | | 2 | [1, 1] | 1 | | 3 | [2] | 2 | | 4 | [1, 1, 1] | 3 | | 5 | [1, 2] | 2 | | 6 | [3] | 3 | | 7 | [1, 1, 1, 1] | 5 | | 8 | [1, 1, 2] | 4 | | 9 | [1, 3] | 3 | | 10 | [2, 2] | 2 | | 11 | [4] | 4 | | 12 | [1, 1, 1, 1, 1] | 7 | | 13 | [1, 1, 1, 2] | 6 | | 14 | [1, 1, 3] | 5 | | 15 | [1, 2, 2] | 5 | | 16 | [1, 4] | 4 | | 17 | [2, 3] | 3 | | 18 | [5] | 5 | | 19 | [1, 1, 1, 1, 1, 1] | 9 | | 20 | [1, 1, 1, 1, 2] | 8 | | 21 | [1, 1, 1, 3] | 7 | | 22 | [1, 1, 2, 2] | 6 | | 23 | [1, 1, 4] | 6 | | 24 | [1, 2, 3] | 6 | | 25 | [1, 5] | 5 | | 26 | [2, 2, 2] | 6 | | 27 | [2, 4] | 4 | | 28 | [3, 3] | 3 | | 29 | [6] | 6 | +----+--------------------+------+
Links
- User baseman101, The Bridge and Torch Problem, Programming Puzzles & Code Golf Stack Exchange.
- Wikipedia, Bridge and torch problem.
Programs
-
Julia
function BT(p) n = length(p) p[end] = -(sum(p) + (n > 2 ? (n-3) * p[1] : 0)) if n >= 3 q = 2p[2] - p[1]; tog = false for k in n-1:-1:1 (tog = ~tog) && p[k] > q ? p[k] -= q : p[k] = 0 end end -sum(p) end [BT(p) for n in 1:9 for p in A026791(n)] |> println # Peter Luschny, Oct 18 2019
Extensions
Terms a(45) and beyond added using Erwan's program from CodeGolf StackExchange by Andrey Zabolotskiy, Oct 18 2019