Skip to content

Instantly share code, notes, and snippets.

@kyleplo

kyleplo/README.md

Created November 26, 2023 19:40
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save kyleplo/d793e30f6f136680f6325a36575ee393 to your computer and use it in GitHub Desktop.
Save kyleplo/d793e30f6f136680f6325a36575ee393 to your computer and use it in GitHub Desktop.
Download ZIP
What if "The Twelve Days of Christmas" had even more gifts?
Raw
README.md

In the song "The Twelve Days of Christmas," a total of 364 gifts are given. However, the majority of those gifts are of living things (turtle doves, maids a milking, etc). Don't those creatures deserve gifts too? Then how many gifts would there be?

This is a programming problem to find the answer. Assume that every gift given get all of the gifts of a lower number than it (ex. a French hen gets two turtle doves and a partridge in a pear tree). Those gifts also need gifts though (ex. those two turtle doves also get their own partridges in pear trees), and so on, all the way down. Golden rings however, being inanimate objects, do not need any gifts. Additionally, partridges in pear trees do not get any gifts, as they are the first gift. With all of these additional gifts, how many gifts would be given in total through the course of the song?

Hints

  • Dynamic programming is going to be your friend here
  • First figure out how to calculate the 364 gifts in the normal version of the song, then build off of that
  • Use the examples I've given above to debug

Example

  • On the third day of Christmas, the narrator of the song is given three French hens.

    Each of those French hens is given two turtle doves, making for six turtle doves in total.

    Each of those turtle doves is given a partridge in a pear tree, making for six partridges in pear trees in total.

  • The narrator is also given two turtle doves.

    Each of those turtle doves is given a partridge in a pear tree, making for two partridges in pear trees in total.

  • The narrator is also given their own partridge in a pear tree.

All of these added up makes for twenty gifts on the third day of Christmas.

Example 2

Here's another example if you're stuck, for the sixth day of Christmas:

  • On the sixth day of Christmas, the narrator is given six geese a laying.

    Each of those geese a laying is given five golden rings, making for 30 golden rings.

    Golden rings are inanimate objects and do not get given anything.

  • The narrator is also given five golden rings.

    Golden rings are inanimate objects and do not get given anything.

  • The narrator is also given four a calling birds.

    Each of those a calling birds is given three French hens, making for 12 French hens.

    Each of those French hens is given two turtle doves, making for 24 turtle doves.

    Each of those turtle doves is given a partridge in a pear tree, making for 24 partridges in pear trees.

  • The narrator is also given three French hens.

    Each of those French hens is given two turtle doves, making for six turtle doves.

    Each of those turtle doves is given a partridge in a pear tree, making for six partridges in pear trees.

  • The narrator is also given two turtle doves.

    Each of those turtle doves is given a partridge in a pear tree, making for two partridges in pear trees.

  • The narrator is also given their own partridge in a pear tree.

All of these add up to 125 gifts on the sixth day of Christmas.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment