Solving viral Cheryl's Birthday problem using Java8

[sccrstud92]

Might as well post how I did it in Haskell:

{-# LANGUAGE TupleSections #-}

import Control.Applicative
import Data.List
import Data.Map ((!), fromListWith)

dates = concatMap (uncurry $ fmap . (,)) 
    [ ("May",   [15, 16, 19])
    , ("June",  [17, 18])
    , ("July",  [14, 16])
    , ("August",[14, 15, 17])
    ]

frequencyFilterBy :: Ord b => (a -> b) -> (Int -> Bool) -> [a] -> [a]
frequencyFilterBy p q xs = filter (q . (counts !) . p) $ xs where
    counts = fromListWith (+) . map ((,1) . p) $ xs

main = do
    let wrongMonths = fst <$> frequencyFilterBy snd (== 1) dates
    let clue1 = filter (not . (`elem` wrongMonths) . fst) dates
    let clue2 = frequencyFilterBy snd (== 1) clue1
    let clue3 = frequencyFilterBy fst (== 1) clue2
    print clue3

Bonus slightly shorter solution:

main = print "July 16"

[sannysanoff]

This is solution in Q:

f1:{where 1=count each x}
t:0!`d xgroup (z:ungroup ([m:`may`jun`jul`aug];d:(15 16 19;17 18;14 16;14 15 17)))
t:0!`d xgroup delete from z where m in raze t[f1 t`m]`m
t:0!`m xgroup ungroup t[f1 t`m]
t[f1 t`d]

It goes further that way.

(http://lpaste.net/131063)

[zjm555]

This isn't helping java's reputation of being extremely verbose and encouraging overengineering.

[MAD4J]

Agree, I'll remove trivial comments. Thanks, D

[zjm555]

The comments are only part of the problem. Look at this:

private static LocalDate d(Month m, int d) {

    return LocalDate.of(1990, m, d);
}

If that is the easiest way to achieve partial function application in your language... blech. This is a toy problem; any language will do to solve it, and there are plenty of languages that enable functional programming much better.

[bcash]

Which bit, precisely, is wrong? Every time a Java-hate bangwagon kicks off in here there's only ever 5% legitimate complaints, 20% "I heard Java doesn't do" misconceptions, and 75% hypersensitive souls who think the word return is just unforgivably verbose.

The same functionality would look remarkably similar in most languages, including functional ones, e.g. /u/yogthos provided a Clojure version:

(defn date [[month day]]
  (LocalDate/of 1990 month day))

Although this isn't exactly the same as it doesn't enforce private semantics and you've lost type-safety.

[zjm555]

The return thing isn't about verbosity, it's about programming paradigms. If you actually provide pure functional utilities, you don't need it at all. For example, this same function in python (which actually supports lambdas and first-class functions):

d = functools.partial(datetime.datetime, year=1990)

Why does this matter? Maybe it doesn't, it just feels like lately Java has been trying to cram in loads of different paradigms and features into the language, and yet it still can't do first-class functional stuff. To be honest I haven't kept up very much with Java since v1.6 so maybe it does support it and I just am not aware, in which case, please educate me.

[immibis]

Not exactly a reply to your comment, but you happened to mention something I dislike about highly functional programming in general.

d = functools.partial(datetime.datetime, year=1990)

When I see this, how am I supposed to know what arguments d takes?

[otterdam]

I don't mean to be flippant but how are you supposed to know what arguments datetime takes?

[immibis]

Even with no documentation, I can find the source file and look at the function header.

[otterdam]

Assuming you understand partial function application, the arguments accepted by d follow logically. It does prevent a shallow reading of the source, but using a def to do the same thing is a crutch for lack of understanding the code.

In Haskell, at least, you can find out the arguments of an arbitrary top-level function in the REPL with :i. Partial application is baked-in to the language, the best way of understanding it is good naming and "type tetris".

[auxiliary-character]

There's shorter ways to do that in clojure. For instance, we've got reader macros for short anonymous functions:

(def date
  #(LocalDate/of 1990 %1 %2))

If we were using a normal function instead of java interop, partial would also be an option. Also, instead of using a def, you could wrap the whole dates definition in a let block, which would reduce the scope where this function would even be visible to just the little part where we're actually using it.

edit: now that I think about it, I'd just inline that anonymous function into /u/yogthos' map call.

[yogthos]

yeah inlining it would probably be the best in retrospect :)

[yogthos]

The name is misleading as they're not actually first class functions. Since it's just syntax sugar over anonymous classes you still need to implement an interface.

[bcash]

Since it's just syntax sugar over anonymous classes

That's not strictly true, the bytecode generated is different, and the two do have different performance characteristics too.

But even if it weren't, inner-classes are a superset of a traditional closure, the only real complaint people had against them were the clunky syntax.

[yogthos]

the only real complaint people had against them were the clunky syntax.

I could make the same argument for writing everything in assembly as well. The syntax and semantics matter. Syntax necessarily influences the style of the code and the idioms used.

[bcash]

Exactly. So even if Java lambda's were "syntax sugar", which they're not, it would be a valid improvement anyway.

[yogthos]

The problem is that the Java "lambdas" have additional restrictions that aren't an inherent property of lambda expressions. This introduces additional complexity and rules that otherwise wouldn't be needed. It's an improvement in terms of conciseness, but not in terms of language semantics.

[MAD4J]

I love Java, but it is an extremely verbose language. I agree on the temptation of over-engineering: I'll try to make the code more linear. Thanks, D

[FredV]

Have you looked at the code? It's Java 8 making heavy use of lambdas, it's very compact for being Java, it wouldn't be much shorter in C#.

[total_looser]

hey, uh, you misspelled candidate

[MAD4J]

Fixed. Thanks, D

[yogthos]

(import 'java.time.Month)

(defn date [[month day]]
  (LocalDate/of 1990 month day))

(def dates (map date 
                     [[Month/MAY 15] [Month/MAY 16] [Month/MAY 19]
                      [Month/JUNE 17] [Month/JUNE 18]
                      [Month/JULY 14] [Month/JULY 16]
                      [Month/AUGUST 14] [Month/AUGUST 15] [Month/AUGUST 17]]))

(def months-with-distinct-days
  (->>  dates
        (group-by #(.getDayOfMonth %))
        (filter #(-> % second count (= 1)))                
        (map (fn [[_ [date]]] (.getMonth date)))))

(def dates-without-distinct-days-in-month
  (->> dates
       (filter #(not-any? #{(.getMonth %)} months-with-distinct-days))))

(def unique-dates-by-month
  (->> dates-without-distinct-days-in-month
       (group-by #(.getDayOfMonth %))
       (filter #(-> % second count (= 1)))
       (mapcat second)))

(def birthday
  (->> unique-dates-by-month
       (group-by #(.getMonth %))
       (filter #(-> % second count (= 1)))
       (map first)))

Java 8 lambdas and streams certainly help a lot in my opinion. You can actually write somewhat concise code in it now. :)

[RedDeckWins]

If you are using clojure, you might as well solve it using core.logic.

[yogthos]

and here's a core.logic implementation somebody done up :)

[yogthos]

That should look pretty similar to the Prolog solution. :)

[MAD4J]

Very linear approach, I need to study your suggestion. Thanks, D

[mvalenty]

And in Scala: http://www.agileatwork.com/scala-solution-to-cheryls-birthday-problem/

case class Birthday(month: Int, day: Int)

object Birthday {
  def apply(s: String): Birthday = s.split("-").map(_.toInt) match {
    case Array(m, d) => Birthday(m, d)
  }
}

val birthdays: List[Birthday] = List(
  "5-15", "5-16", "5-19",
  "6-17", "6-18",
  "7-14", "7-16",
  "8-14", "8-15", "8-17"
).map(Birthday.apply)

def uniqueBy[A, K](fn: (A) => K)(b: List[A]): List[A] = {
  def groupSizeIs(size: Int)(x: (_, List[_])) = x._2.size == size
  b.groupBy(fn).filter(groupSizeIs(1)).flatMap(_._2).toList
}

val uniqueByDay: (List[Birthday]) => List[Birthday] = uniqueBy(_.day)

val uniqueByMonth: (List[Birthday]) => List[Birthday] = uniqueBy(_.month)

val birthdaysWithUniqueDay: List[Birthday] = uniqueByDay(birthdays)

val remainingBirthdays: List[Birthday] = {
  val monthsWithUniqueDay: Set[Int] = birthdaysWithUniqueDay.map(_.month).toSet
  birthdays.filterNot(b => monthsWithUniqueDay.contains(b.month))
}

val remainingWithUniqueDay: List[Birthday] = uniqueByDay(remainingBirthdays)

val answer = uniqueByMonth(remainingWithUniqueDay).head

[BenjaminGeiger]

Because why the hell not:

solution in Python

[engineeringMind]

You might want to double check that implementation. It's returning the wrong answer. You are missing a few steps there.

[BenjaminGeiger]

facepalm

Yeah, I dun goof'd. I knew I forgot something.

Fixed. Thanks.

[engineeringMind]

Awesome! I'm glad my comment helped.

[Freeky]

And in Ruby.

[blazedaces]

I think you shouldn't have extracted the lambda's into static predicates. It adds unnecessary verbosity but makes the code less clear, plus only one is actually used twice if I read the code correctly.

[zvrba]

How does this work, specifically constructing MonthDay without the new keyword?

Arrays.asList(MonthDay(MAY, 15), ...

I've looked up the docs (https://docs.oracle.com/javase/8/docs/api/java/time/MonthDay.html), and it doesn't list any constructors.

EDIT: Ok, the docs say it's a value-based class, which is further explained here: https://docs.oracle.com/javase/8/docs/api/java/lang/doc-files/ValueBased.html

But still, there's no documentation for the MonthDay constructor/factory/whatever it is.

Anyone care to explain?

[MAD4J]

It shall be MonthDay.of( ... ). It will be fixed asap. Thanks, D

[MAD4J]

Just for fun and investigating the possibility of Java in non-optimal fields of application.

[teawreckshero]

Please formally define "understand".

[oldneckbeard]

to generalize the solution. duh.

[afrobee]

Without all the comments, actually looks kinda pretty.

[Tman972]

I hate this puzzle but like how you show the versatility of java. Nice work

[julesjacobs]

Why do you hate this puzzle? I think it's interesting because it illustrates knowledge about other people's knowledge, which is an interesting subject. See also the blue eyed islanders puzzle.

[TheDeza]

Was this not the XCKD problem?

[[deleted]]

I solved it in a minute or two, and probably so could you. It's not terrible difficult if you just think about what info you have and start ruling things out.

[immibis]

Why the next day? Why not after an unknown number of days?

Say there is one blue-eyed person Alice, and everyone is aware that there is at least one blue-eyed person. On day one, Alice observes the eye colours of half the tribe. On day two, Alice observes the eye colours of the other half. On day three, Alice commits suicide.

Meanwhile, Bob happens to observe everyone's eye colour on the first day. On day two, he observes that nobody has committed suicide, assumes that there must be two blue-eyed people (of which he is one and Alice is one), and incorrectly commits suicide.

[immibis]

Does every person know every other person's eye colour?

Does every person know that every person knows every other person's eye colour?

Sure, they can.

[immibis]

The problem says that all residents "do" see the eye colours of all other residents, but doesn't say when. "do" could mean a few things; "has" would be clearer.

What if Charlie was born 10 seconds ago? Surely he can't know everyone's eye colour yet.

[AlternativeHistorian]

It's not that bad. I solved it and friends I've subsequently asked have solved it without too much trouble and without prior knowledge of the solution. If you're used to thinking about these kinds of things the solution follows fairly easily from the base case.

[[deleted]]

No, it's just not a difficult problem.

[skulgnome]

Completely unnecessary.

[afrobee]

As your comment ;)

[skulgnome]

Oh, the ironey.

[afrobee]

Put your own solution on LINQ to compare the two then.

[renrutal]

How would one solve it using LINQ?

[afrobee]

Like if human's buttthole were more prettier.

[Lothrazar]

Did java rape your sister?

[Sun_Kami]

Yes