#339 Fireworks Grand finale

Using ruby to find the best fireworks grand finale; cassidoo’s interview question of the week (2025-07-06). This time I turned off the AI and enjoyed thinking about the deceptively simple algorithmic challenge from first principles.

Notes

The interview question of the week (2025-07-06):

Given an array of fireworks representing a series going off, write a function to find the “grand finale” of the show! A grand finale is defined as the longest sub-array where the average size is at least 5, the minimum velocity is 3, and the difference between the min and max height is no more than 10. Return the starting index of the grand finale.

Example:

const fireworks = [ {height: 10, size: 6, velocity: 4}, {height: 13, size: 3, velocity: 2}, {height: 17, size: 6, velocity: 3}, {height: 21, size: 8, velocity: 4}, {height: 19, size: 5, velocity: 3}, {height: 18, size: 4, velocity: 4} ];

grandFinaleStart(fireworks) 2

PS: if you actually want FIREWORKS, I followed this up with an Arduino implementation with fireworks simulation on an LED matrix. See LEAP#777 GrandFinale.

Initial Analysis and Solution

An eligible “grand finale” sub-array must meet the following criteria:

• average(size) >= 5
• minimum(velocity) == 3
• maximum(height) - minimum(height) <= 10

If this was a real problem, my “requirements analyst alarm” would be ringing, especially for the “minimum velocity is 3” requirement. It seems unusual for that to be the one requirement expressed as an exact match, while the others are expressed as upper or lower limits. I would want to ask for clarification; should it be, for example: “minimum velocity is at least 3”?

For my purposes here, I will start by taking the requirement at face value, and perhaps code a variant later. So minimum(velocity) == 3 it is!

One may initially think that a limited scan would be sufficient: just iterate over elements until the criteria are not met. However the calculation is complicated by the fact we have one criteria using an aggregate function (average(size) >= 5). This raises the possibility that a shorter “invalid” sub-array can become part of a longer “valid” sub-array as more elements are added that skew the average size upwards. For example:

This shows how one outlier (size: 50) can rescue an otherwise failing sub-array, and even carry over for subsequent elements that are trying to bring the average back down.

The implication is that for every starting position, we really can’t avoid checking all the way to the end of the array to see if a longer sub-array is possible. At least that would be the naïve approach. A smarter approach may be to recognise that it is only necessary to keep checking when we know there are elements later in the array that could possibly pull the average back up. I will leave that optimisation for later (maybe).

See examples.rb for the initial solution, It is a fairly naïve approach, but I have included some obvious optimisations:

• size, height, velocity are split into distinct number arrays making it easier to evaluate
• skip the evaluation of sub-arrays if they would not result in a longer match
• evaluate each candidate sub-array immediately, and only record the result if it is better; throw away the rest

Let’s try it with the example provided. The data is in data_eg1.json:

$ ./examples.rb data_eg1.json
Using algorithm: initial_solution
Input array: [{"height"=>10, "size"=>6, "velocity"=>4}, {"height"=>13, "size"=>3, "velocity"=>2}, {"height"=>17, "size"=>6, "velocity"=>3}, {"height"=>21, "size"=>8, "velocity"=>4}, {"height"=>19, "size"=>5, "velocity"=>3}, {"height"=>18, "size"=>4, "velocity"=>4}]
Longest sub-array found: {:start=>2, :finish=>5, :length=>4}
Result: 2

That’s correct, now let’s run it with the skewed average example above, with data in data_eg2.json. Also correct:

$ ./examples.rb data_eg2.json
Using algorithm: initial_solution
Input array: [{"height"=>1, "size"=>5, "velocity"=>3}, {"height"=>1, "size"=>1, "velocity"=>3}, {"height"=>1, "size"=>1, "velocity"=>3}, {"height"=>1, "size"=>1, "velocity"=>3}, {"height"=>1, "size"=>2, "velocity"=>3}, {"height"=>1, "size"=>50, "velocity"=>3}, {"height"=>1, "size"=>3, "velocity"=>3}]
Longest sub-array found: {:start=>0, :finish=>6, :length=>7}
Result: 0

I’ve setup some extended validation in test_examples.rb:

$ ./test_examples.rb
Run options: --seed 54948

# Running:

.....

Finished in 0.000281s, 17793.5943 runs/s, 17793.5943 assertions/s.

5 runs, 5 assertions, 0 failures, 0 errors, 0 skips

More Optimizations?

Some possible optimisations that come to mind:

• transform the data into a form that is easier to process. A few options:
  • put the data in a Matrix object for column-wise processing
  • or consider narray or numo-narray gems
  • or switch to python and numpy
• short-circuit evaluation if it is known that a deficient average size cannot be recovered (the issue discussed above)
• and clarify the requirement: “minimum velocity is 3” or “minimum velocity is at least 3”

I haven’t implemented any of these (yet).

Example Code

Final code is in examples.rb:

#!/usr/bin/env ruby
require 'json'

class GrandFinale
  attr_reader :input
  attr_reader :logging

  def initialize(input, logging = false)
    @input = input
    @logging = logging
  end

  def max_length
    @max_length ||= input.size
  end

  def input_sizes
    @input_sizes ||= input.map { |item| item['size'] }
  end

  def input_heights
    @input_heights ||= input.map { |item| item['height'] }
  end

  def input_velocities
    @input_velocities ||= input.map { |item| item['velocity'] }
  end

  def log_result(result)
    puts "Longest sub-array found: #{result}" if logging
  end

  def valid?(start, finish)
    sizes = input_sizes[start..finish]
    heights = input_heights[start..finish]
    velocities = input_velocities[start..finish]

    average_size = sizes.sum / sizes.size.to_f
    minimum_velocity = velocities.min
    maximum_height = heights.max
    minimum_height = heights.min

    average_size >= 5 &&
    minimum_velocity == 3 &&
    maximum_height - minimum_height <= 10
  end

  def initial_solution
    result = {length: 0}
    max_length.times do |start|
      (start..max_length - 1).each do |finish|
        length = finish - start + 1
        result = {start: start, finish: finish, length: length} if length > result[:length] && valid?(start, finish)
      end
    end
    log_result(result)
    result[:start]
  end
end

if __FILE__==$PROGRAM_NAME
  (puts "Usage: ruby #{$0} (json-file) (algorithm)"; exit) unless ARGV.length > 0
  json_file_name = ARGV[0]
  algorithm = ARGV[1] || 'initial_solution'
  begin
    input = JSON.parse(File.read(json_file_name))
  rescue
    puts "Error: Invalid JSON file - #{json_file_name}"
    exit
  end
  puts "Using algorithm: #{algorithm}"
  calculator = GrandFinale.new(input, true)
  puts "Input array: #{calculator.input.inspect}"
  puts "Result: #{calculator.send(algorithm)}"
end

Credits and References

• cassidoo’s interview question of the week (2025-07-06)
• LEAP#777 GrandFinale - same challenge, but solved on an Arduino with Fireworks simulation.