Project Euler Problem 22

home > Project Euler >

Problem 22

ファイル中の全名前のスコアの合計を求めよ

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2022

5000個以上の名前が書かれている46Kのテキストファイル names.txt を用いる. まずアルファベット順にソートせよ.

のち, 各名前についてアルファベットに値を割り振り, リスト中の出現順の数と掛け合わせることで, 名前のスコアを計算する.

たとえば, リストがアルファベット順にソートされているとすると, COLINはリストの938番目にある. またCOLINは $3 + 15 + 12 + 9 + 14 = 53$ という値を持つ. よってCOLINは $938 \times 53 = 49714$ というスコアを持つ.

ファイル中の全名前のスコアの合計を求めよ.

Names scores

http://projecteuler.net/problem=22

Using names.txt (right click and 'Save Link/Target As...'), a 46K text file containing over five-thousand first names, begin by sorting it into alphabetical order. Then working out the alphabetical value for each name, multiply this value by its alphabetical position in the list to obtain a name score.

For example, when the list is sorted into alphabetical order, COLIN, which is worth $3 + 15 + 12 + 9 + 14 = 53$ , is the 938th name in the list. So, COLIN would obtain a score of $938 \times 53 = 49714$ .

What is the total of all the name scores in the file?

VBScript

JScript

Perl

PHP

Python

Ruby

PowerShell

Scala

更新日 : 2013.02.05

まづは、ファイルの読み込み

scala> var source = scala.io.Source.fromFile("D:\\Euler\\022\\names.txt")
source: scala.io.BufferedSource = non-empty iterator

scala> val name_list = source.getLines.toList.flatMap(_.replaceAll("\"", "").split(','))
name_list: List[String] = List(MARY, PATRICIA, LINDA, BARBARA, ELIZABETH, JENNIFER, MARIA, SUSAN, MARGARET, DOROTHY, LISA, NANCY, KAREN, BETTY, HELEN, SANDRA, DONNA, CAROL, RUTH, SHARON, MICHELLE, LAURA, SARAH, KIMBERLY, DEBORAH, JESSICA, SHIRLEY, CYNTHIA, ANGELA, MELISSA, BRENDA, AMY, ANNA, REBECCA, VIRGINIA, KATHLEEN, PAMELA, MARTHA, DEBRA, AMANDA, STEPHANIE, CAROLYN, CHRISTINE, MARIE, JANET, CATHERINE, FRANCES, ANN, JOYCE, DIANE, ALICE, JULIE, HEATHER, TERESA, DORIS, GLORIA, EVELYN, JEAN, CHERYL, MILDRED, KATHERINE, JOAN, ASHLEY, JUDITH, ROSE, JANICE, KELLY, NICOLE, JUDY, CHRISTINA, KATHY, THERESA, BEVERLY, DENISE, TAMMY, IRENE, JANE, LORI, RACHEL, MARILYN, ANDREA, KATHRYN, LOUISE, SARA, ANNE, JACQUELINE, WANDA, BONNIE, JULIA, RUBY, LOIS, TINA, PHYLLIS, NORMA, PAULA, DIANA, ANNIE, LI...
scala> source.close

ソート

scala> name_list.sorted
res1: List[String] = List(AARON, ABBEY, ABBIE, ABBY, ABDUL, ABE, ABEL, ABIGAIL, ABRAHAM, ABRAM, ADA, ADAH, ADALBERTO, ADALINE, ADAM, ADAN, ADDIE, ADELA, ADELAIDA, ADELAIDE, ADELE, ADELIA, ADELINA, ADELINE, ADELL, ADELLA, ADELLE, ADENA, ADINA, ADOLFO, ADOLPH, ADRIA, ADRIAN, ADRIANA, ADRIANE, ADRIANNA, ADRIANNE, ADRIEN, ADRIENE, ADRIENNE, AFTON, AGATHA, AGNES, AGNUS, AGRIPINA, AGUEDA, AGUSTIN, AGUSTINA, AHMAD, AHMED, AI, AIDA, AIDE, AIKO, AILEEN, AILENE, AIMEE, AISHA, AJA, AKIKO, AKILAH, AL, ALAINA, ALAINE, ALAN, ALANA, ALANE, ALANNA, ALAYNA, ALBA, ALBERT, ALBERTA, ALBERTHA, ALBERTINA, ALBERTINE, ALBERTO, ALBINA, ALDA, ALDEN, ALDO, ALEASE, ALEC, ALECIA, ALEEN, ALEIDA, ALEISHA, ALEJANDRA, ALEJANDRINA, ALEJANDRO, ALENA, ALENE, ALESHA, ALESHIA, ALESIA, ALESSANDRA, ALETA, ALETHA, ALETHEA, ALE...

名前とリスト中の出現順との組を作る

scala> name_list.sorted.zipWithIndex
res2: List[(String, Int)] = List((AARON,0), (ABBEY,1), (ABBIE,2), (ABBY,3), (ABDUL,4), (ABE,5), (ABEL,6), (ABIGAIL,7), (ABRAHAM,8), (ABRAM,9), (ADA,10), (ADAH,11), (ADALBERTO,12), (ADALINE,13), (ADAM,14), (ADAN,15), (ADDIE,16), (ADELA,17), (ADELAIDA,18), (ADELAIDE,19), (ADELE,20), (ADELIA,21), (ADELINA,22), (ADELINE,23), (ADELL,24), (ADELLA,25), (ADELLE,26), (ADENA,27), (ADINA,28), (ADOLFO,29), (ADOLPH,30), (ADRIA,31), (ADRIAN,32), (ADRIANA,33), (ADRIANE,34), (ADRIANNA,35), (ADRIANNE,36), (ADRIEN,37), (ADRIENE,38), (ADRIENNE,39), (AFTON,40), (AGATHA,41), (AGNES,42), (AGNUS,43), (AGRIPINA,44), (AGUEDA,45), (AGUSTIN,46), (AGUSTINA,47), (AHMAD,48), (AHMED,49), (AI,50), (AIDA,51), (AIDE,52), (AIKO,53), (AILEEN,54), (AILENE,55), (AIMEE,56), (AISHA,57), (AJA,58), (AKIKO,59), (AKILAH,60), (AL,...

組を取得

scala> name_list.sorted.zipWithIndex(0)
<console>:10: error: type mismatch;
 found   : Int(0)
 required: scala.collection.generic.CanBuildFrom[List[String],(?, Int),?]
              name_list.sorted.zipWithIndex(0)
                                            ^

scala> val name_index = name_list.sorted.zipWithIndex
name_index: List[(String, Int)] = List((AARON,0), (ABBEY,1), (ABBIE,2), (ABBY,3), (ABDUL,4), (ABE,5), (ABEL,6), (ABIGAIL,7), (ABRAHAM,8), (ABRAM,9), (ADA,10), (ADAH,11), (ADALBERTO,12), (ADALINE,13), (ADAM,14), (ADAN,15), (ADDIE,16), (ADELA,17), (ADELAIDA,18), (ADELAIDE,19), (ADELE,20), (ADELIA,21), (ADELINA,22), (ADELINE,23), (ADELL,24), (ADELLA,25), (ADELLE,26), (ADENA,27), (ADINA,28), (ADOLFO,29), (ADOLPH,30), (ADRIA,31), (ADRIAN,32), (ADRIANA,33), (ADRIANE,34), (ADRIANNA,35), (ADRIANNE,36), (ADRIEN,37), (ADRIENE,38), (ADRIENNE,39), (AFTON,40), (AGATHA,41), (AGNES,42), (AGNUS,43), (AGRIPINA,44), (AGUEDA,45), (AGUSTIN,46), (AGUSTINA,47), (AHMAD,48), (AHMED,49), (AI,50), (AIDA,51), (AIDE,52), (AIKO,53), (AILEEN,54), (AILENE,55), (AIMEE,56), (AISHA,57), (AJA,58), (AKIKO,59), (AKILAH,60)...
scala> name_index(0)
res4: (String, Int) = (AARON,0)

名前のスコアを計算

scala> "ABC".toCharArray.map(_.toInt)
res5: Array[Int] = Array(65, 66, 67)

scala> "ABC".toCharArray.map(_.toInt - 64).toList.sum
res6: Int = 6

scala> val t = name_index(937)
t: (String, Int) = (COLIN,937)

scala> t._1.toCharArray.map(_.toInt - 64).toList.sum * (t._2 + 1)
res7: Int = 49714

名前のスコアを集計

scala> name_index.map(t => t match {case (x,y) => x.toCharArray.map(_.toInt - 64).toList.sum * (y + 1)})
res8: List[Int] = List(49, 70, 57, 120, 200, 48, 140, 328, 396, 350, 66, 168, 1014, 644, 285, 320, 391, 414, 703, 820, 567, 704, 1058, 1200, 850, 910, 1053, 700, 841, 1590, 1736, 1056, 1551, 1632, 1820, 2232, 2442, 1938, 2184, 2800, 2296, 1596, 1978, 2728, 3375, 1794, 4277, 4416, 1323, 1550, 510, 780, 1007, 1944, 2530, 2576, 1881, 2204, 708, 2820, 2562, 806, 2394, 2688, 1820, 1914, 2211, 2924, 3726, 1120, 4118, 4248, 4891, 6068, 6450, 5548, 3003, 1404, 2844, 2560, 3483, 1722, 2573, 3108, 2720, 4730, 5742, 7832, 7120, 2970, 3367, 4232, 5115, 4418, 8930, 3744, 4559, 5096, 5544, 4200, 4343, 8568, 8240, 9256, 5460, 7420, 8774, 9612, 5014, 5170, 6216, 6832, 2486, 2622, 2990, 3480, 4095, 3186, 4403, 4920, 5082, 5612, 6150, 7316, 6375, 8820, 7747, 5504, 5934, 6370, 3406, 5280, 6517, 7504, 5940...
scala> name_index.map(t => t match {case (x,y) => x.toCharArray.map(_.toInt - 64).toList.sum * (y + 1)}).sum
res9: Int = 871198282

F#

更新日 : 2013.02.05

まづは、ファイルの読み込み

> let lines = System.IO.File.ReadAllLines @"D:\Euler\022\names.txt"
- ;;

val lines : string [] =
  [|""MARY","PATRICIA","LINDA","BARBARA","ELIZABETH","JENNIFER","M"+[46386 chars]|]

> let name_list = lines |> Array.map(fun s -> s.Replace("\"","").Split(',') |> Array.toList) |> Array.toList |> List.collect id
- ;;

val name_list : string list =
  ["MARY"; "PATRICIA"; "LINDA"; "BARBARA"; "ELIZABETH"; "JENNIFER"; "MARIA";
   "SUSAN"; "MARGARET"; "DOROTHY"; "LISA"; "NANCY"; "KAREN"; "BETTY"; "HELEN";
   "SANDRA"; "DONNA"; "CAROL"; "RUTH"; "SHARON"; "MICHELLE"; "LAURA"; "SARAH";
   "KIMBERLY"; "DEBORAH"; "JESSICA"; "SHIRLEY"; "CYNTHIA"; "ANGELA"; "MELISSA";
   "BRENDA"; "AMY"; "ANNA"; "REBECCA"; "VIRGINIA"; "KATHLEEN"; "PAMELA";
   "MARTHA"; "DEBRA"; "AMANDA"; "STEPHANIE"; "CAROLYN"; "CHRISTINE"; "MARIE";
   "JANET"; "CATHERINE"; "FRANCES"; "ANN"; "JOYCE"; "DIANE"; "ALICE"; "JULIE";
   "HEATHER"; "TERESA"; "DORIS"; "GLORIA"; "EVELYN"; "JEAN"; "CHERYL";
   "MILDRED"; "KATHERINE"; "JOAN"; "ASHLEY"; "JUDITH"; "ROSE"; "JANICE";
   "KELLY"; "NICOLE"; "JUDY"; "CHRISTINA"; "KATHY"; "THERESA"; "BEVERLY";
   "DENISE"; "TAMMY"; "IRENE"; "JANE"; "LORI"; "RACHEL"; "MARILYN"; "ANDREA";
   "KATHRYN"; "LOUISE"; "SARA"; "ANNE"; "JACQUELINE"; "WANDA"; "BONNIE";
   "JULIA"; "RUBY"; "LOIS"; "TINA"; "PHYLLIS"; "NORMA"; "PAULA"; "DIANA";
   "ANNIE"; "LILLIAN"; "EMILY"; "ROBIN"; ...]

ソートして、名前とリスト中の出現順との組を作る

> let name_index = List.zip (List.sort name_list) [1.. List.length name_list]
- ;;

val name_index : (string * int) list =
  [("AARON", 1); ("ABBEY", 2); ("ABBIE", 3); ("ABBY", 4); ("ABDUL", 5);
   ("ABE", 6); ("ABEL", 7); ("ABIGAIL", 8); ("ABRAHAM", 9); ("ABRAM", 10);
   ("ADA", 11); ("ADAH", 12); ("ADALBERTO", 13); ("ADALINE", 14); ("ADAM", 15);
   ("ADAN", 16); ("ADDIE", 17); ("ADELA", 18); ("ADELAIDA", 19);
   ("ADELAIDE", 20); ("ADELE", 21); ("ADELIA", 22); ("ADELINA", 23);
   ("ADELINE", 24); ("ADELL", 25); ("ADELLA", 26); ("ADELLE", 27);
   ("ADENA", 28); ("ADINA", 29); ("ADOLFO", 30); ("ADOLPH", 31); ("ADRIA", 32);
   ("ADRIAN", 33); ("ADRIANA", 34); ("ADRIANE", 35); ("ADRIANNA", 36);
   ("ADRIANNE", 37); ("ADRIEN", 38); ("ADRIENE", 39); ("ADRIENNE", 40);
   ("AFTON", 41); ("AGATHA", 42); ("AGNES", 43); ("AGNUS", 44);
   ("AGRIPINA", 45); ("AGUEDA", 46); ("AGUSTIN", 47); ("AGUSTINA", 48);
   ("AHMAD", 49); ("AHMED", 50); ("AI", 51); ("AIDA", 52); ("AIDE", 53);
   ("AIKO", 54); ("AILEEN", 55); ("AILENE", 56); ("AIMEE", 57); ("AISHA", 58);
   ("AJA", 59); ("AKIKO", 60); ("AKILAH", 61); ("AL", 62); ("ALAINA", 63);
   ("ALAINE", 64); ("ALAN", 65); ("ALANA", 66); ("ALANE", 67); ("ALANNA", 68);
   ("ALAYNA", 69); ("ALBA", 70); ("ALBERT", 71); ("ALBERTA", 72);
   ("ALBERTHA", 73); ("ALBERTINA", 74); ("ALBERTINE", 75); ("ALBERTO", 76);
   ("ALBINA", 77); ("ALDA", 78); ("ALDEN", 79); ("ALDO", 80); ("ALEASE", 81);
   ("ALEC", 82); ("ALECIA", 83); ("ALEEN", 84); ("ALEIDA", 85);
   ("ALEISHA", 86); ("ALEJANDRA", 87); ("ALEJANDRINA", 88); ("ALEJANDRO", 89);
   ("ALENA", 90); ("ALENE", 91); ("ALESHA", 92); ("ALESHIA", 93);
   ("ALESIA", 94); ("ALESSANDRA", 95); ("ALETA", 96); ("ALETHA", 97);
   ("ALETHEA", 98); ("ALETHIA", 99); ("ALEX", 100); ...]

組を取得

> name_index.[0]
- ;;
val it : string * int = ("AARON", 1)

名前のスコアを計算

> "ABC".ToCharArray();;
val it : char [] = [|'A'; 'B'; 'C'|]
> "ABC".ToCharArray() |> Array.map(int);;
val it : int [] = [|65; 66; 67|]
> "ABC".ToCharArray() |> Array.map(fun n -> (int n) - 64);;
val it : int [] = [|1; 2; 3|]
> "ABC".ToCharArray() |> Array.toList |> List.map(fun n -> (int n) - 64) |> List.sum;;
val it : int = 6

名前のスコアを集計

> name_index |> List.map(fun (x, y) -> x.ToCharArray() |> Array.toList |> List.map(fun n -> (int n) - 64) |> List.sum);;
val it : int list =
  [49; 35; 19; 30; 40; 8; 20; 41; 44; 35; 6; 14; 78; 46; 19; 20; 23; 23; 37;
   41; 27; 32; 46; 50; 34; 35; 39; 25; 29; 53; 56; 33; 47; 48; 52; 62; 66; 51;
   56; 70; 56; 38; 46; 62; 75; 39; 91; 92; 27; 31; 10; 15; 19; 36; 46; 46; 33;
   38; 12; 47; 42; 13; 38; 42; 28; 29; 33; 43; 54; 16; 58; 59; 67; 82; 86; 73;
   39; 18; 36; 32; 43; 21; 31; 37; 32; 55; 66; 89; 80; 33; 37; 46; 55; 47; 94;
   39; 47; 52; 56; 42; ...]
> name_index
- |> List.map(fun (x, y) ->
-    (x.ToCharArray()
-    |> Array.toList
-    |> List.map(fun n ->
-        (int n) - 64)
-    |> List.sum) * y)
- |> List.sum
- ;;
val it : int = 871198282

C

C++

C++Builder

VC++

C#

Java

Objective-C

D

VB

VB.NET

Delphi

Ada

PL/SQL

T-SQL

スクリプト系

VBScript
JScript
Perl
PHP
Python
Ruby
PowerShell

関数型

Scala
F#

C, Java 系

C
C++
C++Builder
VC++
C#
Java
Objective-C
D

Pascal, Basic 系

VB
VB.NET
Delphi
Ada
PL/SQL
T-SQL