Fusing Fireworks

Overview

Given a list of fireworks a-z and times 3-78, arrange them with fuses to make them all light up at the correct time.

A line of input is given as space separated letters and numbers:

a 3 b 6 c 6 d 8 e 9 f 9

That example shows that firework a need to light at time 3, b and c both at 6, d at 8, with e and f both at 9. Each line corresponds to one map.

Output is a fuse/firework map for each line, using the symbols |- to show fuses and the letters to show fireworks.

A - fuse connects to fuses and fireworks directly left/right of it, while a | fuse connects with those above/below. For example, the fuses || are not connected, and -| are.

For example, two possible answers to the above are:

---a        ---------f
|         |||   ||
|-c       |||   de
--|--d      a||
| b |        |c
f   e        b

All fuse maps should start with a single - in the upper left corner. That is the point where you light the fuse. Each character of fuse takes one second to burn. As you can see, the a is reached in three seconds in both diagrams, b in six, etc.

Now, both of the maps given above are valid for the input given, but one is clearly more efficient. The left one only uses 13 units of fuse, while the right one takes 20.

Fuses do not burn through fireworks! So, for input a 3 b 5, this is not valid:

---a--b

Challenge

Your goal is to minimize the amount of fuse used over all test cases. Scoring is very simple, the total units of fuse used.

If you cannot produce a map for a test case, whether it's an impossible case or not, the score for that case is the sum of all times (41 for the example above).

In the case of a tie, the scoring is modified so that the most compact maps win. The tiebreak score is the area of the bounding box of each map. That is, the length of the longest line times the number of lines. For "impossible" maps this is the square of the largest number (81 for the example above).

In the case that submissions tie both of these scoring methods, the tie goes to the earlier entry/edit.

Your program must be deterministic, for verification purposes.

Test Cases

There are 250 test cases, located here. Each has between 4 and 26 fireworks. The minimum fuse time for a firework is 3. The fireworks in each case are "sorted" by time and letter, meaning b will never light before a.

When posting, please include your full program, your total score, and the resulting map for (at least) the first test case given in the file:

a 6 b 8 c 11 d 11 e 11 f 11 g 12 h 15 i 18 j 18 k 21 l 23 m 26 n 28 o 28 p 30 q 32 r 33 s 33 t 34
• Can arbitrarily many fireworks go off at the same time? – Ingo Bürk Aug 8 '14 at 18:27
• Basically, yes. I haven't looked for the largest instance of that in my test cases, but I know it's at least four. The time between two fuses is rand.nextInt(5)%4, so 40% chance of 0, and 20% for each 1,2,3. – Geobits Aug 8 '14 at 18:30
• Just an suggestion: I'd use a '+' for where the fuses connect or change direction, that would make the output graphics IMHO much more intuitive! – flawr Aug 8 '14 at 19:01
• @flawr I'll allow that, provided it's done in a way that doesn't change the score. For instance, -+- in place of --- would not automatically connect fireworks above/below, there still has to be a | above/below to connect it to a firework. -+- in place of -|- is okay as it is. – Geobits Aug 8 '14 at 19:41
• Are all of the test cases solvable? E.g. if there were five or more fireworks to go off at time 3, I don't think you could fit them all near enough to the start. Likewise, you might be able to fit all of them but they might block the way to the outside for later fireworks. – Martin Ender Aug 9 '14 at 12:15

Total Length: 9059, Total Area: 27469, Failures: 13.

Note: Score includes failure penalties.

Sample output:

a 6 b 8 c 11 d 11 e 11 f 11 g 12 h 15 i 18 j 18 k 21 l 23 m 26 n 28 o 28 p 30 q 32 r 33 s 33 t 34
------ae
| |
|---c
b||-g
|d|
f |
i---|
k---| h
|  j
|---m
l  | t
o-n|
|s-r
|-|
p q
Length: 39, Area: 150.

a 6 b 6 c 6 d 6 e 6 f 6 g 6 h 8 i 9 j 9 k 9 l 12 m 12 n 13 o 14 p 15 q 15 r 15 s 17 t 17 u 17 v 17 w 17 x 20 y 23 z 26
------a  n|--w
|d-||---k|-o|
| g|b  |--m --x
|-|c    ||--r|
||f     l|-q |
||--j u--|--s|-
e|-i    |p|  y|
h      v t  z-
Length: 56, Area: 120.

Full output: http://pastebin.com/raw.php?i=spBUidBV

Don't you just love brute-force solutions? This is a little more than a simple backtracking algorithm: our tireless worker moves around the map, placing fuses and fireworks as necessary, while testing all possible moves at any point. Well, almost---we do restrict the set of moves and abandon nonoptimal states early so that it doesn't take unbearably long (and, in particular, so that it terminates.) Special care is taken not to create any cycles or unintended paths and not to go back the same way we came, so it's guaranteed that we don't visit the same state twice. Even so, finding an optimal solution can take a while, so we eventually give up on optimizing a solution if it takes too long.

This algorithm still has some headroom. For one thing, better solutions can be found by increasing the FRUSTRATION parameters. There's no competition ATM but these numbers can be cranked up if and when...

Compile with: g++ fireworks.cpp -ofireworks -std=c++11 -pthread -O3.

Run with: ./fireworks.

Reads input from STDIN and writes output to STDOUT (possibly out-of-order.)

/* Magic numbers */
/* When FRUSTRATION_MOVES moves have passed since the last solution was found,
* the last (1-FRUSTRATION_STATES_BACKOFF)*100% of the backtracking states are
* discarded and FRUSTRATION_MOVES is multiplied by FRUSTRATION_MOVES_BACKOFF.
* The lower these values are, the faster the algorithm is going to give up on
* searching for better solutions. */
#define FRUSTRATION_MOVES 1000000
#define FRUSTRATION_MOVES_BACKOFF 0.8
#define FRUSTRATION_STATES_BACKOFF 0.5

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <mutex>
#include <string>
#include <sstream>
#include <cassert>

using namespace std;

/* A tile on the board. Either a fuse, a firework, an empty tile or an
* out-of-boudns tile. */
struct tile {
/* The tile's value, encoded the "obvious" way (i.e. '-', '|', 'a', etc.)
* Empty tiles are encoded as '\0' and OOB tiles as '*'. */
char value;
/* For fuse tiles, the time at which the fuse is lit. */
int time;

operator char&() { return value; }
operator const char&() const { return value; }

bool is_fuse() const { return value == '-' || value == '|'; }
/* A tile is vacant if it's empty or OOB. */
bool is_vacant() const { return !value || value == '*'; }

/* Prints the tile. */
template <typename C, typename T>
friend basic_ostream<C, T>& operator<<(basic_ostream<C, T>& os,
const tile& t) {
return os << (t.value ? t.value : ' ');
}
};
/* Fireworks have the same encoding as tiles. */
typedef tile firework;
typedef vector<firework> fireworks;

/* The fuse map. It has physical dimensions (its bounding-box) but is
* conceptually infinite (filled with empty tiles.) */
class board {
/* The tiles, ordered left-to-right top-to-bottom. */
vector<tile> p_data;
/* The board dimensions. */
int p_width, p_height;
/* The total fuse length. */
int p_length;

public:
board(): p_width(0), p_height(0), p_length(0) {}

/* Physical dimensions. */
int width() const { return p_width; }
int height() const { return p_height; }
int area() const { return width() * height(); }
/* Total fuse length. */
int length() const { return p_length; }

/* Returns the tile at (x, y). If x or y are negative, returns an OOB
* tile. */
tile get(int x, int y) const {
if (x < 0 || y < 0)
return {'*'};
else if (x >= width() || y >= height())
return {'\0'};
else
return p_data[y * width() + x];
}
/* Sets the tile at (x, y). x and y must be nonnegative and the tile at
* (x, y) must be empty. */
board& set(int x, int y, const tile& t) & {
assert(x >= 0 && y >= 0);
assert(!get(x, y));
if (x >= width() || y >= height()) {
int new_width = x >= width() ? x + 1 : width();
int new_height = y >= height() ? y + 1 : height();
vector<tile> temp(new_width * new_height, {'\0'});
for (int l = 0; l < height(); ++l)
copy(
p_data.begin() + l * width(),
p_data.begin() + (l + 1) * width(),
temp.begin() + l * new_width
);
p_data.swap(temp);
p_width = new_width;
p_height = new_height;
}
p_data[y * width() + x] = t;
if (t.is_fuse())
++p_length;
return *this;
}
board&& set(int x, int y, const tile& t) && { return move(set(x, y, t)); }

/* Prints the board. */
template <typename C, typename T>
friend basic_ostream<C, T>& operator<<(basic_ostream<C, T>& os,
const board& b) {
for (int y = 0; y < b.height(); ++y) {
for (int x = 0; x < b.width(); ++x)
os << b.get(x, y);
os << endl;
}
return os;
}
};

/* A state of the tiling algorithm. */
struct state {
/* The current board. */
board b;
/* The next firework to tile. */
fireworks::const_iterator fw;
/* The current location. */
int x, y;
/* The current movement direction. 'N'orth 'S'outh 'E'ast, 'W'est or
* 'A'ny. */
char dir;
};

/* Adds a state to the state-stack if its total fuse length and bounding-box
* area are not worse than the current best ones. */
void add_state(vector<state>& states, int max_length, int max_area,
state&& new_s) {
if (new_s.b.length() < max_length ||
(new_s.b.length() == max_length && new_s.b.area() <= max_area)
)
states.push_back(move(new_s));
}
/* Adds the state after moving in a given direction, if it's a valid move. */
void add_movement(vector<state>& states, int max_length, int max_area,
const state& s, char dir) {
int x = s.x, y = s.y;
char parallel_fuse;
switch (dir) {
case 'E': if (s.dir == 'W') return; ++x; parallel_fuse = '|'; break;
case 'W': if (s.dir == 'E') return; --x; parallel_fuse = '|'; break;
case 'S': if (s.dir == 'N') return; ++y; parallel_fuse = '-'; break;
case 'N': if (s.dir == 'S') return; --y; parallel_fuse = '-'; break;
}
const tile t = s.b.get(s.x, s.y), nt = s.b.get(x, y);
assert(t.is_fuse());
if (nt.is_fuse() && !(t == parallel_fuse && nt == parallel_fuse))
add_state(states, max_length, max_area, {s.b, s.fw, x, y, dir});
}
/* Adds the state after moving in a given direction and tiling a fuse, if it's a
* valid move. */
void add_fuse(vector<state>& states, int max_length, int max_area,
const state& s, char dir, char fuse) {
int x = s.x, y = s.y;
int sgn;
bool horz;
switch (dir) {
case 'E': ++x; sgn = 1; horz = true; break;
case 'W': --x; sgn = -1; horz = true; break;
case 'S': ++y; sgn = 1; horz = false; break;
case 'N': --y; sgn = -1; horz = false; break;
}
if (s.b.get(x, y))
/* Tile is not empty. */
return;
/* Make sure we don't create cycles or reconnect a firework. */
const tile t = s.b.get(s.x, s.y);
assert(t.is_fuse());
if (t == '-') {
if (horz) {
if (fuse == '-') {
if (!s.b.get(x + sgn, y).is_vacant() ||
s.b.get(x, y - 1) == '|' ||
s.b.get(x, y + 1) == '|')
return;
} else {
if (s.b.get(x + sgn, y) == '-' ||
!s.b.get(x, y - 1).is_vacant() ||
!s.b.get(x, y + 1).is_vacant())
return;
}
} else {
if (!s.b.get(x, y + sgn).is_vacant() ||
s.b.get(x - 1, y) == '-' ||
s.b.get(x + 1, y) == '-')
return;
}
} else {
if (!horz) {
if (fuse == '|') {
if (!s.b.get(x, y + sgn).is_vacant() ||
s.b.get(x - 1, y) == '-' ||
s.b.get(x + 1, y) == '-')
return;
} else {
if (s.b.get(x, y + sgn) == '|' ||
!s.b.get(x - 1, y).is_vacant() ||
!s.b.get(x + 1, y).is_vacant())
return;
}
} else {
if (!s.b.get(x + sgn, y).is_vacant() ||
s.b.get(x, y - 1) == '|' ||
s.b.get(x, y + 1) == '|')
return;
}
}
/* Ok. */
states,
max_length,
max_area,
{board(s.b).set(x, y, {fuse, t.time + 1}), s.fw, x, y, dir}
);
}
/* Adds the state after adding a firework at the given direction, if it's a
* valid move. */
void add_firework(vector<state>& states, int max_length, int max_area,
const state& s, char dir) {
int x = s.x, y = s.y;
int sgn;
bool horz;
switch (dir) {
case 'E': ++x; sgn = 1; horz = true; break;
case 'W': --x; sgn = -1; horz = true; break;
case 'S': ++y; sgn = 1; horz = false; break;
case 'N': --y; sgn = -1; horz = false; break;
}
if (s.b.get(x, y))
/* Tile is not empty. */
return;
/* Make sure we don't run into an undeliberate fuse. */
if (horz) {
if (s.b.get(x + sgn, y) == '-' || s.b.get(x, y - 1) == '|' ||
s.b.get(x, y + 1) == '|')
return;
} else {
if (s.b.get(x, y + sgn) == '|' || s.b.get(x - 1, y) == '-' ||
s.b.get(x + 1, y) == '-')
return;
}
/* Ok. */
states,
max_length,
max_area,
/* After adding a firework, we can move in any direction. */
{board(s.b).set(x, y, {*s.fw}), s.fw + 1, s.x, s.y, 'A'}
);
}
void add_possible_moves(vector<state>& states, int max_length, int max_area,
const state& s) {
/* We add the new states in reverse-desirability order. The most
* (aesthetically) desirable states are added last. */

const tile t = s.b.get(s.x, s.y);
assert(t.is_fuse());

/* Move in all (possible) directions. */
for (char dir : "WENS")
if (dir) add_movement(states, max_length, max_area, s, dir);

/* If the fuse is too short for the next firework, keep adding fuse. */
if (t.time < s.fw->time) {
if (t == '-') {
add_fuse(states, max_length, max_area, s, 'N', '|');
add_fuse(states, max_length, max_area, s, 'S', '|');
add_fuse(states, max_length, max_area, s, 'W', '|');
add_fuse(states, max_length, max_area, s, 'W', '-');
add_fuse(states, max_length, max_area, s, 'E', '|');
add_fuse(states, max_length, max_area, s, 'E', '-');
} else {
add_fuse(states, max_length, max_area, s, 'W', '-');
add_fuse(states, max_length, max_area, s, 'E', '-');
add_fuse(states, max_length, max_area, s, 'N', '-');
add_fuse(states, max_length, max_area, s, 'N', '|');
add_fuse(states, max_length, max_area, s, 'S', '-');
add_fuse(states, max_length, max_area, s, 'S', '|');
}
} else if (t.time == s.fw->time) {
/* If we have enough fuse for the next firework, place the firework (if
* possible) and don't add more fuse, or else we'll never finish... */
if (t == '-') {
add_firework(states, max_length, max_area, s, 'W');
add_firework(states, max_length, max_area, s, 'E');
} else {
add_firework(states, max_length, max_area, s, 'N');
add_firework(states, max_length, max_area, s, 'S');
}
}
}

void thread_proc(mutex& lock, int& total_length, int& total_area,
int& failures) {
fireworks fw;
vector<state> states;

while (true) {
/* Read input. */
string input;
{
lock_guard<mutex> lg(lock);

while (!cin.eof() && input.empty())
getline(cin, input);
if (input.empty())
break;
}
fw.clear();
int length = 0, area;
{
stringstream is;
is << input;
while (!is.eof()) {
char c;
int t;
if (is >> c >> t) {
/* Fireworks must be sorted by launch time. */
assert(fw.empty() || t >= fw.back().time);
fw.push_back({c, t});
length += t;
}
}
assert(!fw.empty());
area = fw.back().time * fw.back().time;
}

/* Add initial state. */
states.push_back({board().set(0, 0, {'-', 1}), fw.begin(), 0, 0, 'A'});

board solution;
int moves = 0;
int frustration_moves = FRUSTRATION_MOVES;

while (!states.empty()) {
/* Check for solutions (all fireworks consumed.) */
while (!states.empty() && states.back().fw == fw.end()) {
state& s = states.back();
/* Did we find a better solution? */
if (solution.area() == 0 || s.b.length() < length ||
(s.b.length() == length && s.b.area() < area)
) {
solution = move(s.b);
moves = 0;
length = solution.length();
area = solution.area();
}
states.pop_back();
}

/* Expand the top state. */
if (!states.empty()) {
state s = move(states.back());
states.pop_back();
add_possible_moves(states, length, area, s);
}

/* Getting frustrated? */
++moves;
if (moves > frustration_moves) {
/* Get rid of some data. */
states.erase(
states.begin() + states.size() * FRUSTRATION_STATES_BACKOFF,
states.end()
);
frustration_moves *= FRUSTRATION_MOVES_BACKOFF;
moves = 0;
}
}

/* Print solution. */
{
lock_guard<mutex> lg(lock);

cout << input << endl;

if (solution.area())
cout << solution;
else {
cout << "FAILED!" << endl;
++failures;
}

cout << "Length: " << length <<
", Area: " << area <<
"." << endl << endl;
total_length += length;
total_area += area;
}
}
}

int main(int argc, const char* argv[]) {
mutex lock;
int total_length = 0, total_area = 0, failures = 0;

for (int i = 0; i < THREAD_COUNT; ++i)
ref(total_area), ref(failures));
for (int i = 0; i < THREAD_COUNT; ++i)

cout << "Total Length: " << total_length <<
", Total Area: " << total_area <<
", Failures: " << failures <<
"." << endl;
}

Total Length: 17387, Total Area: 62285, Failures: 44.

Sample output:

a 6 b 8 c 11 d 11 e 11 f 11 g 12 h 15 i 18 j 18 k 21 l 23 m 26 n 28 o 28 p 30 q 32 r 33 s 33 t 34
------a
|----f
|---c
b|||---h
|dg  |
e    |-j
|---k
i  |
|---m
l  |-o
|--p
n |--s
|-r
q|
t
Length: 45, Area: 345.

Full output: http://pastebin.com/raw.php?i=mgiqXCRK

For reference, here's a much simpler approach. It tries to connect fireworks to a single main fuse line, creating a "staircase" shape. If a firework can't connect to the main line directly (which happens when two or more fireworks light at the same time) it traces back the main line looking for a point where it can branch perpendicularly down or to the right (and fails if no such point exists.)

Unsurprisingly, it does worse than the brute-force solver, but not by a huge margin. Honestly, I expected the difference to be somewhat bigger.

Run with: python fireworks.py.

from __future__ import print_function
import sys

total_length = total_area = failures = 0

for line in sys.stdin:
line = line.strip()
if line == "": continue
fws = line.split(' ')
# The fireworks are a list of pairs of the form (<letter>, <time>).
fws = [(fws[i], int(fws[i + 1])) for i in xrange(0, len(fws), 2)]

# The board is a dictionary of the form <coord>: <tile>.
# The first tile marks the "starting point" and is out-of-bounds.
board = {(-1, 0): '*'}
# The tip of the main "staircase" fuse.
tip_x, tip_y = -1, 0
tip_time = 0
# We didn't fail. Yet...
failed = False

for (fw, fw_time) in fws:
dt = fw_time - tip_time
# Can we add the firework to the main fuse line?
if dt > 0:
# We can. Alternate the direction to create a "staircase" pattern.
if board[(tip_x, tip_y)] == '-':    dx, dy = 0, 1; fuse = '|'
else:                               dx, dy = 1, 0; fuse = '-'
x, y = tip_x, tip_y
tip_x += dt * dx
tip_y += dt * dy
tip_time += dt
else:
# We can't. Trace the main fuse back until we find a point where we
# can thread, or fail if we reach the starting point.
x, y = tip_x, tip_y
while board[(x, y)] != '*':
horz = board[(x, y)] == '-'
if horz:    dx, dy = 0, 1; fuse = '|'
else:       dx, dy = 1, 0; fuse = '-'
if dt > 0 and (x + dx, y + dy) not in board: break
if horz:    x -= 1
else:       y -= 1
dt += 1
if board[(x, y)] == '*':
failed = True
break
# Add the fuse and firework.
for i in xrange(dt):
x += dx; y += dy
board[(x, y)] = fuse
board[(x + dx, y + dy)] = fw

# Print output.
print(line)
if not failed:
max_x, max_y = (max(board, key=lambda p: p[i])[i] + 1 for i in (0, 1))
for y in xrange(max_y):
for x in xrange(max_x):
print(board.get((x, y), ' '), end = "")
print()
length = len(board) - len(fws) - 1
area = max_x * max_y
else:
print("FAILED!")
failures += 1
length = sum(map(lambda fw: fw, fws))
area = fws[-1] ** 2
print("Length: %d, Area: %d.\n" % (length, area))
total_length += length; total_area += area

print("Total Length: %d, Total Area: %d, Failures: %d." %
(total_length, total_area, failures))
• Out of curiosity, how long does this take to complete with the current parameters? – Geobits Aug 9 '14 at 16:11
• @Geobits: It's machine-dependent, obviously, and I didn't watch too closely, but I think about twenty minutes, give or take. – DarwinBot Aug 9 '14 at 16:16