dvgrn wrote:EDIT: No luck with recipes-including-honeyfarm-elbows at depth 8 -- there are still conflicts in two places, one requiring the elbow to be one step farther away (toward the beginning) and one needing two diagonal steps more clearance (in the usual blocks-and-boats section at the end). But the efficiency ratio has continued to improve:
@depth8: 2678gp / 540g = 4.959259
@depth12: 2668gp / 540g = 4.940741
Finally got a depth3 search to complete without conflicts, using a dodgy hacked version of the search script. @chris_c, thanks for contributing the necessary changes, unless you consider them too embarrassing to publish, in which case I did them all myself.
The cost so far is an extra 238 gliders over the best recipe above:
2906 / 540 = 5.381481
Code: Select all
full_recipe: e16 e46 e9999 o15 e25 e30 e32 e33 e16 e46 o21 e9999 o53 o23 e21 o44 o32 o15 e21 e21 e9999 o53 e19 o26 o25 o27 o34 o20 o23 o43 o9999 o21 e28 e39 e44 o41 e32 o47 o29 e16 o30 o23 o31 o15 e43 o22 e9999 e20 e39 e36 o16 o71 e18 o19 o42 o53 e36 o18 o20 o56 e9999 e17 e69 e9999 o31 e24 e19 e68 e36 e15 e49 e26 e15 e17 e9999 e28 o44 e71 o56 e35 e39 e18 e59 o28 e9999 e69 e9999 o21 e22 e69 e9999 o21 e22 o41 e67 o33 o9999 e29 e20 e16 e69 e9999 o29 o17 o23 e29 e23 o26 e9999 e69 e9999 o29 e27 e42 e54 e34 o47 e16 e48 e19 e42 e18 e26 e19 e25 e15 o17 e71 e23 e9999 e54 e48 e19 e53 o15 e15 o44 e15 e16 o30 o22 e21 o18 e16 e43 o29 e25 o18 e45 e19 e55 o15 e69 e9999 o19 e35 e15 e17 o54 e23 o9999 e31 e24 e25 o34 e9999 e26 e25 e27 e34 e9999 e21 o28 o26 e49 o20 o22 e9999 e20 e18 e19 o18 e48 o23 e68 o18 o40 o42 e25 o20 o9999 e19 e68 o25 o30 o22 e15 o9999 o15 o15 o27 o31 e24 e23 e21 o18 e59 o28 e58 e9999 o20 o56 o18 o16 o46 e68 o19 e43 o45 o9999 e58 e24 e23 e21 o18 e59 o28 e9999 o37 o16 e48 e49 o55 e9999 e69 e9999 o31 e24 e16 o44 e71 o56 e23 e16 e66 o15 e16 e20 e23 e33 e27 o40 e25 e71 o9999 e15 e30 e21 e17 e33 o32 e9999 e20 e33 e40 e18 o40 e25 e71 o9999 o15 o30 o21 o22 o9999 e15 o20 o15 e15 e9999 o18 e45 e16 o27 o21 e9999 o21 e15 e9999 e54 e48 e19 e31 e36 o67 o29 e9999 o30 e23 e16 e66 o29 e27 o44 e71 o56 e23 o34 e9999 e17 o40 e20 e22 e20 e23 e31 o18 e16 e26 o20 o56 o35 o39 o35 o9999 o22 o15 o21 e15 e69 e9999 o54 e18 o31 e24 e23 e21 o22 e19 e55 o9999 o20 o56 e23 e16 e66 o29 e27 e43 o9999 e55 o16 e17 e20 e23 e52 o15 e20 e72 o27 e48 o20 o56 e23 e16 o46 o51 o26 o33 o16 o9999 e31 o15 o26 o56 o9999 o21 e19 e68 e20 e18 e46 e21 e26 e15 e30 e21 e22 e15 e21 o15 e69 e9999 o53 o18 e9999 o48 e23 o68 e18 o21 e34 o19 o15 e44 e20 e56 e9999 e21 o22 o9999 e15 o20 o15 e69 e9999 o29 o17 o23 e29 e23 o21 e22 e9999 e21 o28 o26 e49 o20 o56 e9999 e21 e22 e15 e21 o15 o69 o9999 e29 o22 o16 e21 e19 o20 e24 e23 o39 e21 e21 e44 e32 o24 e27 e43 o45 o9999 e56 e19 e16 o40 e25 o16 o15 e15 o22 o9999 e15 o20 o15 o41 e67 o33 o9999 e29 o17 o23 e29 e9999 e21 e22 e15 e23 o40 e25 e71 o9999 e15 e18 e9999 o43 e20 e24 e16 e43 o45 o9999 e58 e24 o31 o20 o33 o27 o54 e18 o20 o22 e16 e68 e9999 o33 o39 o15 e43 e21 e35 e27 e45 e69 e9999 o21 e22 o69 o9999 e61 e61 e21 e21 e9999 o53 e19 e9999 e69 e9999 o15 e21 o15 e42 o50 o17 o33 e67 o33 e20 e22 o16 o19 o25 o17 o15 o27 e27 e21 e54 e18 e20 o20 o56 e23 o15 e27 o27 o21 e9999 o21 o21 e20 e18 e46 e21 o17 o23 e29 e23 e16 e66 o21 e22 e15 e9999 o18 e31 e9999 e26 e17 e15 e26 o21 o33 e46 e18 e20 e33 e21 e9999 e27 e43 o45 o15 e27 o27 o21 e9999 o21 o21 e9999 e54 e58 e9999 o31 e24 e19 e68 e20 e72 o27 e48 o20 o56 e23 e16 e66 o29 o24 o18 o9999 o41 e32 o47 o29 o26 o15 o30 o21 e27 o40 e25 e33 o20 o16 e30 e23 e31 e15 o30 o22 e24 o48 o9999 e16 e50 e9999 o29 e67 o35 e28 o49 e19 e68 o20 o56 e35 e39 e18 e34 o36 e69 e9999 o31 e24 e16 o18 e15 o20 o15 o69 o9999 e31 o24 o16 e61 o20 e16 e22 e43 o45 o9999 e59 e16 o40 e25 o16 o15 e34 o20 o9999 o33 o16 o48 o19 o42 o53 e19 o39 o9999 e49 o16 o30 e21 e21 e44 e32 e15 e16 e43 o9999 e60 o53 e19 e17 e16 o53 e52 o20 o56 e9999 e21 e27 o30 o22 e21 o18 e21 e23 e26 e15 e26 o16 o27 o21 o54 o18 o20 e20 e72 o27 e48 o20 o56 o9999 o15 o15 o30 e18 o22 o20 o23 o31 e18 o16 e50 e20 e9999 e21 o28 o39 o44 e66 e9999 o31 e26 e69 e9999 o31 e24 o29 e67 o35 e28 o49 o16 o43 e45 e15 o32 e29 o34 e43 o54 e9999 e66 e26 o20 o56 e9999 e24 e18 e9999 e69 e9999 o50 e15 e24 e18 o20 o56 e23 e16 e66 o31 o24 e26 e9999 e18 e9999 o50 o9999 o51 o47 o53 e18 e25 e51 e35 e16 o29 e16 e30 e32 e20 o18 e22 e20 e23 e43 o20 o9999 o33 o16 e42 e59 o33 e18 e9999 e37 e9999 o18 e22 o20 o23 o52 e15 e37 e9999 o29 e16 o30 o23 o31 o15 e44 o62 o16 e15 e23 o27 o36 o15 o17 o44 o34 e9999 e21 o28 o26 e49 e20 e22 e9999 e17 e16 o53 e52 o36 o15 o18 o29 e9999 e15 e15 e30 o42 o9999 e16 o40 e25 e71 o9999 e15 e30 e24 e15 e18 o37 o9999 e18 o18 o16 o40 e25 o16 o15 e15 e26 e15 e17 e9999 e28 e27 e21 o9999 e21 e21 e9999 e54 e42 o67 e9999 e21 o28 o26 e49 o20 o56 e23 e16 e66 o29 o37 e9999 o32 o34 e23 e18 o15 e17 e69 e9999 o19 e27 o25 e15 e30 e15 e9999 e26 o20 o56 e23 o23 o17 o23 e29 o23 e34 o9999 o17 e40 o20 o22 e20 e33 e15 e51 e18 e9999 o54 e23 o9999 e21 o22 o69 o9999 e31 e24 e22 e18 e15 e44 o46 o44 e62 e16 e20 e16 e69 e9999 o21 e22 e69 e9999 o53 o18 e9999 o36 o18 o23 e17 e33 o15 e37 e9999 o18 e22 o20 o23 o52 e15 o36 o15 o29 o27 o24 e21 e16 o30 o23 o31 o15 o44 e62 o15 e21 e24 e18 o20 o56 e23 o15 o17 o23 e29 o9999 o17 o69 o9999 e29 e17 e23 o29 e23 o23 e24 e18 o20 o56 e9999 e20 o64 o18 e20 o45 e19 e68 o20 o22 e9999 e37 e9999 o47 e9999 e37 e9999 o18 e45 e16 e42 e54 e34 o47 e15 e16 e19 e9999 e21 e17 e33 o32 e47 e69 e9999 o15 e68 e18 o22 o9999 e23 o18 o41 e16 o40 e25 o16 o15 e15 e16 o30 o23 o31 o15 o44 e71 o42 o37 o9999 e18 o45 o25 e15 o58 o15 e37 e9999 o18 e45 e23 e22 e16 e21 o22 o31 o37 o9999 e49 o9999 e18 o16 e23 o36 o15 o17 o44 o15 e22 e15 e21 o15 e69 e9999 o19 e18 e9999 e15 e16 e59 o33 e9999 o15 o23 e15 o27 e27 e21 e54 e18 e20 o20 o56 o23 e34 e9999 e17 o49 e9999 e15 o22 o9999 e23 o18 o41 o31 o20 o64 o15 o69 e42 e54 e34 o47 e15 e30 e27 o21 e22 e9999 e21 o28 o39 o44 e66 e9999 o53 o42 e15 o21 o15 o27 e46 e9999 e16 e42 e69 e9999 o19 e18 e19 e20 e23 e31 o18 e45 e19 e55 o15 e69 e9999 o21 e22 e69 e9999 o29 e22 e15 e23 e43 o30 o9999 e46 e19 e54 e48 e19 e29 o17 o23 e29 e23 e15 o23 e18 e9999 e15 e16 e44 e15 e54 o39 o9999 e49 e30 o22 o39 o9999 e49 e20 o18 e34 e23 o16 e31 o24 o21 o15 o27 e40 o25 o33 e20 o17 o33 e32 o9999 o38 o31 o9999 o34 e20 e56 e9999 e17 e69 e9999 o61 o43 e48 e20 e9999 o20 o61 e9999 o20 o18 o20 o27 o22 o21 e26 e15 e16 e19 e9999 e17 e69 e9999 o50 e17 e27 e44 o62 e15 e15 e16 e59 o33 e9999 o27 o19 o9999 o17 o33 e32 o47 e51 e47 e53 e18 o9999 e27 e16 e25 o18 e16 o59 e28 o9999 o15 o9999 e18 o22 e20 e23 e31 o18 e22 o20 o23 o31 e18 o22 e20 e23 e31 o18 e16 e59 o33 e34 o34 e26 e20 e18 e16 o67 e33 o16 o25 o21 o17 e59 e53 e60 o15 o15 o16 o15 e18 o16 e50 e55 e15 e20 e9999 e21 o28 o39 o44 o37 e9999 o21 e34 o17 e36 e15 e18 e16 o59 e33 o34 e34 o15 o27 e27 e21 o9999 e21 o15 o17 o16 e46 o9999 o41 e18 e9999 o68 o9999 e42 o40 e20 e23 e33 e17 e35 e19 e53 e20 e43 o45 o15 e27 o27 o21 e9999 o21 e15 e38 e15 e15 e18 e32 e18 e16 o23 o20 o22 e9999 o20 o22 e9999 e37 e9999 o47 e9999 o38 o15 o15 o18 o32 o40 e25 o29 o27 e9999 e35 e26 o44 e62 e28 o16 e19 o43 e54 o9999 o66 o26 e20 e43 e22 o18 e9999 e21 o28 o39 o44 e51 e35 e16 o31 e24 e16 o40 e25 e33 o20 e20 e9999 o20 o56 e23 o26 e9999 e69 e9999 o29 e24 e18 o20 o56 e23 o34 e20 e23 e31 o18 e45 o19 o42 o53 e19 o40 o15 o26 o34 o63 e24 e21 e15 e26 e15 e30 e24 e15 e18 e9999 e69 e9999 o19 e27 o25 e15 e30 e21 e22 e15 e23 o40 e25 e33 o20 e16 o30 o23 o31 o15 o40 o15 e20 e56 e23 e15 o29 e17 o54 o64 o9999 e21 o18 o23 e48 o9999 e29 o58 e19 e68 e9999 o26 o19 o56 o9999 e31 e15 e20 e43 o51 e19 e55 o15 o54 e23 o9999 e31 e24 e19 e68 e36 e15 e29 e27 e20 o21 o21 o44 o32 e24 e22 e9999 e16 o23 o20 o56 e9999 e17 e69 e9999 o29 o17 o23 e28 o23 o16 o66 e53 e18 o9999 e36 e18 e15 e27 e43 o29 e25 o18 e45 e16 e42 e54 e34 o47 e15 e16 e16 e43 o29 e58 e27 o64 e28 e43 o9999 e60 o53 e19 e20 e18 o70 e46 e9999 e17 o40 e20 e22 e20 o9999 e31 o53 e19 e17 e16 o30 o54 e18 o9999 e15 e44 e9999 o27 o43 e45 e9999 o56 o19 e22 o18 o20 o49 e25 o18 e40 o25 o33 e20 e32 o16 e15 e15 e16 e19 e9999 e21 e27 o40 e25 e71 o9999 e15 e30 e21 e27 o27 o21 o54 o18 e31 e16 o40 e25 e71 o9999 o15 o17 o9999 o16 o20 o24 o19 o68 o20 o22 o9999 o17 o16 e53 o52 o9999 o69 o9999 e29 o22 o16 e21 e19 e21 e17 e33 o15 e26 e25 e27 e34 o9999 o17 e49 o9999 o15 o22 o19 o56 o19 e16 o30 o23 o31 o15 e18 e16 o23 e20 e18 o70 o72 o17 o9999 o69 o9999 e29 e24 e18 o20 o56 e23 o26 o20 o18 o16 e67 o33 e16 e56 e38 e44 o40 o44 e62 e16 e17 e33 o15 o20 o56 e9999 e20 o64 o18 e20 o45 o19 o68 o20 o18 o16 e15 e16 e63 e38 e64 e21 o68 o9999 o21 e29 e20 e56 e9999 e17 o54 o57 o28 o15 o29 e32 o30 e15 o20 e9999 o37 o56 e23 e16 e66 o29 o17 o23 e29 o23 e15 e17 e33 o67 e33 e9999 e41 o32 e47 e29 o27 e40 o25 o33 e20 o22 o9999 e15 o20 o15 o69 o9999 e29 o17 o23 e29 e23 o21 e22 e9999 e21 o28 o26 e49 e36 e15 e29 e27 e24 e21 e27 e19 e9999 e27 e42 e54 e34 o47 e15 e30 e26 e41 o22 o16 o34 e15 o20 o22 o19 o56 o19 e26 o16 o63 o38 o64 o9999 e20 e56 o9999 o15 o15 o31 e24 o44 o19 o18 o18 o20 o47 e46 e9999 e16 e42 o54 e23 o9999 e31 e24 e19 e68 o36 o15 o17 o44 o23 e26 o16 o56 o27 o53 e19 o36 o15 o18 o16 e50 e23 e9999 o15 e25 o30 o23 o31 o15 e30 e17 e29 e55 e26 e21 e16 e9999 e16 e9999 e17 e33 o15 o20 o56 o9999 o20 e64 e18 o20 e45 o23 o22 o16 o21 e22 o31 o17 o16 o18 o17 o23 e29 e9999 e17 e54 e48 e19 e29 o27 o42 o54 o34 e47 e15 e16 e19 e9999 e20 o64 o18 e20 o45 e21 e33 e59 o33 e34 o34 e15 o22 o16 e21 e19 o15 o15 o31 e24 o44 o25 e40 o15 e53 o19 e9999 e69 e9999 e20 e25 e26 e15 e16 e19 e9999 e17 e69 e9999 o21 e22 o69 o9999 e31 e24 e16 e46 o29 e30 o18 e45 o23 o21 e18 e19 e31 e24 o9999 e31 e16 e54 e48 e19 e53 e18 e9999 o20 o22 e9999 o20 o56 e9999 e17 o49 e49 e15 o30 e31 e24 e16 e43 o45 o15 e27 o27 o21 o41 o25 o17 e26 e16 e48 e19 e68 e36 e15 e29 e40 o25 e15 o58 o15 e37 e9999 o31 e19 o25 o42 o34 e15 e15 e30 o18 e16 e59 o33 e34 o34 e26 e26 e25 e27 e34 e20 e23 e52 o15 e20 e56 o9999 o20 e24 e23 o39 o15 o9999 o22 o69 o9999 e31 o24 o19 o68 e36 e15 e29 e40 e16 e50 e9999 o31 o36 o15 o19 o21 e19 e68 e20 e72 o27 e48 o20 o56 o9999 o17 e54 o23 e9999 o31 e24 o21 e16 e66 o29 e27 e43 o45 o15 e22 e9999 e16 o23 o20 o22 e9999 o20 o22 o9999 o26 o25 o27 o34 e20 e9999 e33 e16 o42 o59 e28 o36 o20 o9999 e16 e43 o45 o15 e27 o27 o21 o41 o25 o17 e27 e44 o25 e69 e9999 o21 e22 e69 e9999 o19 e27 o25 e15 e26 o21 o33 o19 o31 o24 e9999 o31 e16 o54 e23 o9999 e31 e24 o21 e16 e66 o21 o22 e69 e9999 o29 e20 e9999 e36 e15 e33 o41 e15 o30 o32 o20 e18 o45 e21 o16 o66 o20 e25 e17 e33 o32 e9999 e37 e9999 o18 e22 o20 o23 o31 e18 o16 e26 e17 e16 o53 e52 o39 o9999 e49 e30 o36 e9999 e35 e29 e47 e18 e19 e25 o9999 e31 o20 o9999 o16 o49 o9999 o27 o21 o54 o18 o20 o36 o15 o29 o40 e16 e18 e16 o23 e26 e25 e27 e34 e9999 e17 o40 e20 e22 e20 e23 e31 o18 e45 e16 o46 e18 o48 o71 e16 e48 e19 e55 o9999 e20 e42 o20 o56 e23 e16 e66 o31 e24 e16 o44 e71 o56 e9999 e24 e18 e9999 e69 e9999 o31 e24 o29 e67 o35 e28 o49 e19 e68 e17 e16 o53 e52 e9999 e69 e9999 o29 e27 e61 o16 e48 e33 o17 o16 e46 o9999 o41 e18 o20 o56 e23 e15 e20 e21 e15 e26 o16 o27 o21 o54 o18 o20 e20 e72 o27 e48 o20 o56 o23 o9999 e15 o27 o16 o69 o9999 e15 o16 e20 e23 e52 o15 o20 o33 o21 o9999 o26 o16 o48 o16 e46 o18 e48 e71 e17 e15 e30 e21 e16 o30 o23 o31 o15 e43 o26 e17 e19 e34 e9999 o18 e26 e9999 e69 e9999 o31 e21 e34 e9999 e22 e15 e25 e42 e54 o17 o33 e67 o33 o20 o56 e35 e39 e18 e34 o36 e69 e9999 o29 o27 o43 e45 e15 e27 e42 e9999 e59 o20 e25 e27 o40 e25 e33 o20 e22 e15 e21 o15 e41 o67 e33 e9999 o29 e27 e43 o45 o9999 e58 o19 o24 o29 o9999 o39 e46 o21 e9999 o53 e23 o15 e27 e43 o9999 e60 o53 e19 o39 o9999 e49 o16 o30 e21 e34 e9999 e21 o28 o26 e49 o20 o56 e35 e39 e18 e59 o28 e9999 e54 e48 e19 e15 e16 e20 e23 e52 o15 e37 e9999 o31 e24 e21 e34 e9999 e21 o28 o26 e49 o20 o56 e9999 e24 e18 e9999 e69 e9999 o19 e27 o25 o15 o30 o27 e26 o37 o9999 e18 o45 e21 e26 o37 o9999 e49 e24 o9999 o9999 o21 e28 e26 o49 o20 o56 e9999 e17 e69 e9999 o16 e9999 o29 e22 e9999 o15 e20 e15 e69 e9999 o53 e18 o9999 e36 e18 e15 e16 e30 e32 e20 o18 e45 e19 e55 o15 e69 e9999 o29 o32 o64 o25 e30 o50 o22 o16 e21 e19 e21 e27 o27 o21 o54 o18 o20 e36 e15 e29 e40 o16 o46 e29 o30 e18 o45 e19 e55 o15 e69 e9999 o19 e35 e15 e17 o54 e23 o9999 e21 o18 e15 e16 e15 e51 o20 o22 e9999 e17 e16 o53 e52 o39 o9999 e49 o16 o30 e16 o40 e25 e71 o9999 e17 e15 e30 e30 e9999 e30 e37 e9999 o18 e45 e19 e55 o15 e69 e9999 o29 o27 o42 o54 o34 e47 o16 o19 e25 e17 e67 e23 o15 o22 o16 e21 e19 e21 e22 e15 e21 o15 e68 e9999 o18 e34 o71 e15 o9999 o22 o30 o23 o31 o15 e30 e22 o24 e48 e9999 e16 o30 o22 e21 o18 e16 e61 o29 o20 e16 o30 o22 e21 o18 o15 o9999 o22 o69 o9999 e19 o27 e25 e17 e15 e16 e19 e9999 e17 e69 e9999 o29 e24 e18 o20 o56 e9999 e17 e69 e9999 o31 e24 e16 o44 e71 o56 e9999 e17 e69 e9999 o31 e24 e16 o44 e71 o56 e23 e16 e66 o31 e24 e19 e68 e37 e9999 o31 e24 o31 o35 o36 o61 e50 o19 o68 e37 e9999 o31 e24 e16 o44 e62 e22 e32 o15 e18 o9999 e36 e18 e27 o20 o56 e9999 e24 e18 e37 e9999 o18 e18 e16 o40 e25 o25 e9999 o20 o56 e35 e39 e35 e9999 e17 e33 o32 e9999 e37 e9999 o18 e45 o21 e16 e66 o29 e27 o27 o21 e9999 o21 o21 e9999 e69 e9999 o50 e17 e27 o40 e25 e26 e26 o32 o30 o23 o31 o15 o48 e32 o41 e20 e56 o23 e33 o33 o34 e9999 e22
I'll probably keep wrestling with this problem until I've gotten the cost back down under 5gp/g. Might take another week or so. A depth-6 search already has a fairly nice ratio -- 2706gp / 540g = 5.011111 -- but it breaks in several places in the boats-and-blocks construction. Will probably recompile at something like depth 15, and then just patch in the depth-3 solution for the blocks-and-boats part at the end, unless a lucky nonconflicting recipe shows up at a greater depth.
-- Of course the only problem is that it takes too long to figure out which specific recipes to forbid, when compiling the full recipe at greater depths. It's fairly easy to compile, test, and recompile just blocks-and-boats at a greater depth, starting from a known elbow that's part of an efficient high-depth recipe -- then patch the two partial recipes together. Maybe I'll do something along those lines.
Here's the version of the dodgy hacked search script that successfully found the depth-3 solution. It expects the input recipe to be either in the clipboard or in a file called recipe.txt (but you can type in another filename).
dodgy-search-from-Golly-clipboard.py:
Code: Select all
from collections import defaultdict
import heapq
import sys
import os
from contextlib import contextmanager
import golly as g
RECIPE_FILE = "recipes_0hd.txt"
OUTPUT_FILE = "gp-dodgy-depthX.txt"
RECIPE_PATH = os.path.dirname(os.path.realpath(sys.argv[0]))
SEARCHDEPTH = "6"
USE_0HD = True
# For every recipe that is causing a problem add the glider number to
# the list for that recipe
dodgy_bits = {
"L-11m3CKr" : [ 479 ],
"R-13m-3HDr" : [ 479 ],
"R-13m-6HCr" : [ 479 ],
"L-3m-4HPr" : [ 536 ],
"L-14m19HK" : [ 537, 538 ]
}
recipes = defaultdict(list)
recipe_strings = {}
def dijkstra(elbow, dist, lanes):
routes = {}
q = [(0, len(lanes), elbow, dist, None, None, None)]
while q:
c1, remaining, e1, d1, e0, d0, l0 = heapq.heappop(q)
if (remaining, e1, d1) not in routes:
routes[(remaining, e1, d1)] = c1, e0, d0, l0
if remaining == 0:
return routes, e1, d1
for e2, d2, l1, c2 in recipes[e1]:
if l1 is not None:
lane, exceptions = lanes[-remaining]
if l1 + d1 != lane or (e2, d2, l1, c2) in exceptions:
continue
else:
hit = 1
else:
hit = 0
if (remaining-hit, e2, d1+d2) not in routes:
heapq.heappush(q, (c1 + c2, remaining-hit, e2, d1+d2, e1, d1, l1))
def lookahead(elbow, dist, lanes, parities, lookahead):
plain = ""
allcost = 0
for i in range(len(lanes)):
lookahead_lanes = lanes[i:i+lookahead]
lookahead_gliders = len(lookahead_lanes)
routes, e0, d0 = dijkstra(elbow, dist, lookahead_lanes)
remaining = 0
found_first_glider = False
subplain = ""
ops = ""
# print "Begin backtrace"
while (remaining, e0, d0) != (lookahead_gliders, elbow, dist):
e1, d1 = e0, d0
cost, e0, d0, lane = routes[(remaining, e0, d0)]
# print "\t\t", cost, e0, d0, lane
if lane is not None:
remaining += 1
if remaining == lookahead_gliders and not found_first_glider:
found_first_glider = True
next_cost, next_elbow, next_dist = cost, e1, d1
if found_first_glider:
recipe = recipe_strings[(e0, e1, d1-d0, lane)]
if parities[i]:
recipe = switch_phase(recipe)
g.show(str(len(lanes)-i)+": " + recipe) ###### DMG
subplain = recipe + subplain
ops = "%d %s %d %s %s %d: %s\n" % (allcost+cost,
str(lane),
d1-d0,
e0,
e1,
d1,
recipe) + ops
elbow, dist = next_elbow, next_dist
allcost += next_cost
plain += subplain
print ops,
print "\nfull_recipe: " + plain
print "\n%d / %d = %f" % (allcost, len(lanes), float(allcost) / len(lanes))
# split s into runs of alpha characters followed by non-alpha characters
def to_tokens(s):
if not s:
return []
tokens = []
token = ""
alpha = s[0].isalpha()
for c in s:
if c == ":":
break
if c.isalpha() == alpha:
token += c
else:
tokens.append(token)
token = c
alpha = not alpha
tokens.append(token)
return tokens
def reflect(elbow):
return elbow[0] if elbow[-1] == "r" else elbow + "r"
def reflect_recipe(s):
if USE_0HD:
return s
res = ""
tokens = to_tokens(s)
for i in range(len(tokens)):
if tokens[i] in "oe":
timing = int(tokens[i+1])
if abs(timing) != 9999 and timing % 2:
if tokens[i] == "o":
res += "e"
elif tokens[i] == "e":
res += "o"
else:
res += tokens[i]
elif tokens[i].strip():
res += "%d " % -int(tokens[i])
return res
def switch_phase(recipe):
out_recipe = ""
for c in recipe:
if c == "o":
out_recipe += "e"
elif c == "e":
out_recipe += "o"
else:
out_recipe += c
return out_recipe
def read_recipes(filename):
global lanes
with open(filename) as f:
for s in f:
tokens = to_tokens(s)
if tokens[0] == "Rev":
continue
i = 0
side = lane = None
if tokens[0][0] in "LR":
side = tokens[0][0]
lane = int(tokens[1])
i += 2
assert(tokens[i] == "m")
move = int(tokens[i+1])
elbow_in = tokens[i+2][0]
elbow_out = tokens[i+2][1:]
recipe_string = s[s.find(":")+2:].rstrip("\r\n")
description_string = s[:s.find(":")]
# Uncommment to use only central blocks as elbow
# if tokens[i+2].count("A") != 2:
# continue
cost = s.count("e") + s.count("o")
for c in "RL":
if side is None or side == c:
recipes[elbow_in].append((elbow_out, move, lane, cost))
recipe_strings[(elbow_in, elbow_out, move, lane)] = recipe_string
if description_string in dodgy_bits:
for lane_num in dodgy_bits[description_string]:
lanes[lane_num][1].append((elbow_out, move, lane, cost))
elbow_in = reflect(elbow_in)
elbow_out = reflect(elbow_out)
recipe_string = reflect_recipe(recipe_string)
lanes = []
parities = []
###### DMG changes for Golly clipboard-input version of gp-compile.py ######
@contextmanager
def stdout_redirected(new_stdout):
save_stdout = sys.stdout
sys.stdout = new_stdout
try:
yield None
finally:
sys.stdout = save_stdout
def is_recipe(s):
if ":" in s:
parts=s.rstrip().split(":")
if len(parts)>2:
return False
s=parts[1]
###### Other malformatted data is still possible, but if there aren't any nonconforming
###### characters on the clipboard, the odds are quite good that it's really a recipe
return all(c in "0123456789- EO" for c in s)
rfile=g.getstring("Enter name of glider-pair recipe library to use\n(same directory as script):",RECIPE_FILE)
input_string = g.getclipstr()
if input_string=="": input_string = "recipe.txt"
if os.path.isfile(os.path.join(RECIPE_PATH, input_string)):
with open (os.path.join(RECIPE_PATH, input_string), "r") as f:
input_string=f.read().rstrip()
if not is_recipe(input_string):
input_string = g.getstring("Enter EO-format slow salvo recipe, or filename of a\n" +
"file that contains an EO-recipe, to convert to glider pairs:",
input_string)
if not is_recipe(input_string):
if os.path.isfile(os.path.join(RECIPE_PATH, input_string)):
with open (os.path.join(RECIPE_PATH, input_string), "r") as f:
input_string=f.read().rstrip()
if not is_recipe(input_string):
g.exit("Input recipe is invalid: " + input_string)
outfilename=g.getstring("Enter name of output file to write to\n(same directory as script):",OUTPUT_FILE)
sd=int(g.getstring("Enter depth to search:", SEARCHDEPTH))
if sd<1: g.exit("Invalid search depth " + str(sd)
+"\nShould be greater than 0, and probably less than 20.")
#
# read_recipes(RECIPE_FILE)
#
# input_string = ""
#
# for s in sys.stdin:
# input_string += s
#
###### end of DMG changes ######
idx = input_string.find(":")
if idx >= 0:
input_string = input_string[idx+1:]
tokens = to_tokens(input_string)
for i in range(0, len(tokens), 2):
if "E" in tokens[i]:
parities.append(0)
elif "O" in tokens[i]:
parities.append(1)
else:
assert(False)
# convert from quarter diagonals to half diagonals
lanes.append((int(tokens[i+1]) // 2 + 1, []))
read_recipes(os.path.join(RECIPE_PATH,rfile))
###### DMG was too lazy to change a few print statements... ######
with open(outfilename, "w") as f:
with stdout_redirected(f):
lookahead("A", -33, lanes, parities, sd)
# lookahead("A", -33, lanes, parities, 6)
-- Oh, and I did have to remove one elbow-move recipe from the library:
m5BC: e25 e9999 e39 o20
It was only being used in one place, and it caused a conflict, so there was no harm in taking it out. So far so good...