06 maja 2013

Zliczyć krotność liter w ciągu znaków w Scali

Przyszło mi spędzać coraz więcej czasu ze Scalą ze względu na coraz trudniejsze zadania w szkoleniu Functional Programming Principles in Scala i tym razem trafiłem na ciekawy problem programistyczny, którego rozwiązanie dalekie jestbyło od doskonałości. Coś mi mówiło, że można ładniej, a na pewno skromniej (w sensie "w bardziej zwartej postaci").

Załóżmy, że mamy nieuporządkowaną listę par znak-krotność (typu List[(Char, Int)]), w której można znaleźć pary dla tych samych liter, np.
val l = List(('a',2), ('b',1), ('a',1), ('c',1), ('c', 3), ('e',3))
Jak miałaby wyglądać funkcja, która przyjmuje listę, np. l powyżej, i "normalizuje" ją do postaci uszeregowanego (leksykograficznie) ciągu par, w których na drugiej pozycji jest suma wszystkich krotności dla danego znaku.

Przy założeniu powyższej listy l otrzymalibyśmy wynik:
List((a,3), (b,1), (c,4), (e,3))
Początkowo napisałem takiego potworka, który nie tylko, że nie wyglądał, ale i posiadał błąd (patrz ostatni map z l.length):
(l groupBy { case (c, _) => c }).toList map (e => e._2) map (l => (l.head._1, l.length)) sorted
Obrzydlistwo!

Moje neurony nadawały na zwiększonej częstotliwości, kiedy ślęczałem nad tym problemem, a ostateczny wynik o mało co nie zrzucił mnie z krzesła! Przede wszystkim był mój i dodatkowo działał!

Nie podam jeszcze rozwiązania, aby nie psuć zabawy. Podpowiem, że w moim rozwiązaniu nie zabrakło miejsca dla groupBy, map, funkcji anonimowych z case oraz sum i sorted. W sumie 76 znaków, co wciąż nie zachwyca skromnością. A jak u Ciebie?