Today is my birthday.
Yes, it is actually my birthday: May the 15th. So, I thought it would be fun to write about a little algorithmic puzzle I’ve been pondering about. You see, each year we grow older; as a person, but also collectively as an organisation, a group, a community. That’s a lot of combined knowledge I reckon. 🙂
Take, for instance, my immediate family. My parents Christiaan and Marijke, my little sister Petra and dear girlfriend Jolien. All together, we have a combined age of 234 years! Wow, isn’t that something?
I wondered: at who’s birthday have we reached a grand total of 250 years combined knowledge?
At first I actually just hoped to get a date and a person for conversation making purposes, but pretty soon it became a bit of a personal challenge. I mean: I’m a developer and that shouldn’t be hard to program right?
But: algorithms have never been my strong suit, and I knew that any 1st solution — which would produce an answer — had to be followed by at least a 2nd algorithm taking a different approach, for it actually to be a challenge. There’s never just one way of tackling a puzzle and by pushing myself to always come up with at least 2 alternatives to any problem, I get better at what I do as a software developer.
(Also publishing it on a blog like this and getting feedback is really enlightening!)
So before continuing to read on: try to solve the question for yourself first.
Given the known birthdays of e.g. 5 members of your family, at whose birthday (when and who) for the first time the entire family becomes e.g. 250 years old.
(The number 250 doesn’t really mean anything. ’t Was just a nice, round number we still had lying in front of us, nothing special.)
I have to admit: at first I tried to do this in Microsoft Excel. Unfortunately, after trying to be smart with formulas using other formulas I clearly went insane pretty soon, since I couldn’t actually code my way out of it.
To the code it is….!
Meet the Family’s helper classes & methods
So the 5 members of my family can be modelled in Java with a name, a String
and their birthday, using a LocalDate
, like this:
Family family = new Family(Arrays.asList( new Person("Jolien", LocalDate.of(1984, Month.OCTOBER, 15)), new Person("Petra", LocalDate.of(1983, Month.DECEMBER, 7)), new Person("Ted", LocalDate.of(1981, Month.MAY, 15)), new Person("Christiaan", LocalDate.of(1953, Month.JUNE, 10)), new Person("Marijke", LocalDate.of(1951, Month.JULY, 24)) ));
The OO (Object Orientation)-part of my brain always lights up pretty fast, and devising a Person
and a Family
gave me some room to put some helper-methods in there which I expected I would need pretty soon…;-)
class Family { private List<Person> persons; Family(List<Person> persons) { this.persons = persons; } List<Person> getPersons() { return persons; } void displayBirthDate(LocalDate date) { persons .stream() .filter(p -> p.isBirthDay(date)) .findFirst() .ifPresent(p -> System.out.printf( "Reaching %s when %s turns %s at %s\n", calcTotalAge(date), p.name, p.calcAge(date), date) ); } }
You see I also created a displayBirthDate
which I could feed a possibly found birth date, which is the actual challenge, and find and print the one who’s birthday it is on that day.
And for completeness, here’s the Person
class.
class Person { String name; LocalDate birthDate; Person(String name, LocalDate birthDate) { this.name = name; this.birthDate = birthDate; } boolean isBirthDay(LocalDate date) { return MonthDay.from(date).equals(MonthDay.of( birthDate.getMonth(), birthDate.getDayOfMonth())); } @Override public String toString() { return String.format( "Person(name: %s, birthDate: %s)", name, birthDate ); } }
1st algorithm
My very, very first instinct, after having posed the question to myself — “at what birthday the entire family becomes 250 years of age?” — said: brute force.
I thought I needed to be able to calculate the total age of the family at any given time. This requires also being able to calculate the age of a person at any given time.
I introduced 2 helper methods for this: Family#calcTotalAge
which needs a new Person#calcAge
.
class Family { private List<Person> persons; Family(List<Person> persons) { this.persons = persons; } List<Person> getPersons() { return persons; } int calcTotalAge(LocalDate date) { return persons .stream() .mapToInt(p -> p.calcAge(date)) .sum(); } void displayBirthDate(LocalDate date) { persons .stream() .filter(p -> p.isBirthDay(date)) .findFirst() .ifPresent(p -> System.out.printf( "Reaching %s when %s turns %s at %s\n", calcTotalAge(date), p.name, p.calcAge(date), date) ); } } class Person { String name; LocalDate birthDate; public Person(String name, LocalDate birthDate) { this.name = name; this.birthDate = birthDate; } int calcAge(LocalDate date) { return Period.between(this.birthDate, date).getYears(); } boolean isBirthDay(LocalDate date) { return MonthDay.from(date).equals(MonthDay.of( birthDate.getMonth(), birthDate.getDayOfMonth())); } @Override public String toString() { return String.format( "Person(name: %s, birthDate: %s)", name, birthDate ); } }
And finally the code which does the work of finding me a birth date:
void doBruteForce() { LocalDate foundLuckyDate; LocalDate futureDate = now; while (true) { if (family.calcTotalAge(futureDate) >= 250) { foundLuckyDate = futureDate; break; } futureDate = futureDate.plusDays(1); } family.displayBirthDate(foundLuckyDate); }
The brute force approach by Just. Looping. Days.
Start “now”, increase by one day into the future and calculate the total age of the family every time. Repeat this until we’re 250 years old, break from the loop: we’ve found our lucky birthday.
Yep, this assumes we’re not 250 years yet. If we are, the “>=” (greater than or equal) will save us from an infinite loop 🙂
The application with our main()
method we’re about to run is:
public class WhenAreWe250Years { private final Family family; private final LocalDate now; public WhenAreWe250Years(Family family) { this.family = family; this.now = LocalDate.now(); family.getPersons().stream().forEach(System.out::println); System.out.println( String.format( "Total age now at %s is %s", now, family.calcTotalAge(now)) ); } public static void main(String... args) { Family family = new Family(Arrays.asList( new Person("Jolien", LocalDate.of(1984, Month.OCTOBER, 15)), new Person("Petra", LocalDate.of(1983, Month.DECEMBER, 7)), new Person("Ted", LocalDate.of(1981, Month.MAY, 15)), new Person("Christiaan", LocalDate.of(1953, Month.JUNE, 10)), new Person("Marijke", LocalDate.of(1951, Month.JULY, 24)) )); WhenAreWe250Years app = new WhenAreWe250Years(family); System.out.println("Brute:"); app.doBruteForce(); } void doBruteForce() { LocalDate foundLuckyDate; LocalDate futureDate = now; while (true) { if (family.calcTotalAge(futureDate) >= 250) { foundLuckyDate = futureDate; break; } futureDate = futureDate.plusDays(1); } family.displayBirthDate(foundLuckyDate); } // Person, Family, etc }
After running it, the output to the console looks like:
Person(name: Jolien, birthDate: 1984-10-15) Person(name: Petra, birthDate: 1983-12-07) Person(name: Ted, birthDate: 1981-05-15) Person(name: Christiaan, birthDate: 1953-06-10) Person(name: Marijke, birthDate: 1951-07-24) Total age now at 2018-05-15 is 234 Brute: Reaching 250 when Christiaan turns 68 at 2021-06-10
Woohoo, above code found 2021-06-10.
It doesn’t know which person, but that’s ok: another piece of the code looked that up.
The result is found pretty fast (which is no surprise with this minimalistic amount of iterations) but we had to test 1123 days — the period between now and found date — before it met our condition. It’s not a benchmarking exercise, but having this amount of inefficiency left me with a bitter aftertaste.
I could not just leave it at this, and as I promised myself already, I forced myself to think about a 2nd solution.
Another attempt additionally has to have only one constraint (else I can’t sleep tonight): it has to be smarter.
Version 1b
I came up with refactored version using Streams…
Stream.iterate(now, l -> l.plusDays(1)) .filter(futureDate -> { return family.calcTotalAge(futureDate) >= 250; }) .findFirst() .orElseThrow(RuntimeException::new);
…but that could hardly qualify as a significant other approach. Even IntelliJ can suggest replacing a while
loop using Stream API — and vice versa 🙂
So before continuing to read on: answer another question for yourself first.
Did you also thought up initially something along the lines of brute force checking things until you found the answer? If so, what would be another, possibly smarter, approach?
…
…
…
The 2nd attempt took me hours.
I know a bit of the awesome Java 8 Date Time API nowadays and fiddling around with classes such as Period
and stuff made me believe the answer would be somewhere in those date/time classes.
Well, I just couldn’t find it.
At breaking-point I thought:
- “Isn’t the whole calculation not as simple as finding
x
in a simple math question e.g.Given: 12/x = 4. What is x?
. Boom, just a few expressions using known periods between something and a datex
somewhere in the future?”
Then I thought:
- “We have some birth days ahead of us. The lucky birth date is a certain amount of years from now, which is the nth birth day that year.”
The I started something which has this as the end result:
void doSmarter() { // We have some birth days ahead of us :-) LocalDate firstDayOfYear = now.with(TemporalAdjusters.firstDayOfYear()); int yearsToCover = 250 - family.calcTotalAge(firstDayOfYear); int yearlyAmountOfBirthDays = family.getPersons().size(); // The lucky birth date... // ...is a certain amount of years from now int nthYearFromNow = yearsToCover / yearlyAmountOfBirthDays; // ...which is the nth birth day that year int nthBirthDayThatYear = yearsToCover % yearlyAmountOfBirthDays; // That's it! Family members already ordered by day of birth LocalDate luckyDate = family.getPersons() // ...so take nth person from the (zero-based) list .get(nthBirthDayThatYear - 1) // and calculate his/her birth date in that year .calcNextBirthDate(now, nthYearFromNow); family.displayBirthDate(luckyDate); }
Running it after the initial version, the 2nd version yields the same results:
Brute: Reaching 250 when Christiaan turns 68 at 2021-06-10 Smarter: Reaching 250 when Christiaan turns 68 at 2021-06-10
Woohoo!
I had to go a few times back and forth through the code to get it right — so don’t think this happened in the first pass. It’s again about trying to find a date in the future, but now by trying to reason about what I want to achieve. See the comments in the source code.
First I had the impression that my 2nd version should have made clever use of whatever the Date/Time API of Java had to offer me, but it seemed I was just not creative enough…and came up with some old-school math operations. Man!
Check the variables, as if they were logged at the end of the method, may be it makes more sense to follow what happens, just for background:
now = 2018-05-15 firstDayOfYear = 2018-01-01 yearsToCover = 17 yearlyAmountOfBirthDays = 5 nthYearFromNow = 3 nthBirthDayThatYear = 2 luckyDate = 2021-06-10
The rationale: still 3 years (with all 5 birth days each) had to happen and then only 2 more to “span” the 17 years of difference between total age now (234) and our target age of 250 years.
To find the 2nd birth day in a year, I choose to alter the Family
constructor and ordering set family members then and there by their day of birth throughout the year.
The adjusted constructor which makes earlier logic work:
Family(List<Person> persons) { this.persons = persons.stream() .sorted(Comparator.comparing(p -> p.birthDate.getDayOfYear())) .collect(Collectors.toList()); }
Getting creative!
You can forget the specifics of both solutions pretty fast since those are not important. You might even argue about the aesthetics of the code or not having proper error handling. Yes, the code might fail when ran in, oh say, 2021.
The takeaway for myself is mainly the following: there’s not one solution to a problem and the hard part is, after the initial stab at it, getting creative and finding a 2nd or 3rd alternative. Yes, it will take hours to come up with new alternatives, but what’s the harm in asking a colleague to do the same and cross-referencing your work?
By first doing this for yourself a few times, you’ll notice some juices start to flow and you’ll end up sometimes in a completely different place than where you hoped to end up 🙂
I at least got confirmation that I definitely need to do more algorithmic puzzles every now and then, so even those “math parts” of my brain stay in shape.
Now, who of the readers can come up with a 3rd alternative?
- Excel is accepted too 🙂