home
>
Project Euler
>
ForNext
Shut the fuck up and write some code
Problem 4
最大の回文積
左右どちらから読んでも同じ値になる数を回文数という. 2桁の数の積で表される回文数のうち, 最大のものは である.
では, 3桁の数の積で表される回文数のうち最大のものを求めよ.
Largest palindrome product
A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is .
Find the largest palindrome made from the product of two 3-digit numbers.
VBScript
更新日 : 2013.01.04
「3桁の数の積」ということだが、999 から 100 まで計算する必要もないだろうと...
Option Explicit
Private cnt: cnt = 0
Private max: max = 0
Call main
WScript.Echo "CNT = " & cnt
WScript.Echo "MAX = " & max
Private Sub main()
Dim i
For i = 999 To 900 Step -1
Dim j
For j = 999 To 900 Step -1
cnt = cnt + 1
Dim n: n = i * j
Dim s: s = CStr(n)
If s = StrReverse(s) Then
If max < n Then
WScript.Echo CStr(i) & " * " & CStr(j) & " = " & s
max = n
End If
End If
Next
Next
End Sub
D:\study\Project Euler\004>cscript //nologo 004.vbs 993 * 913 = 906609 CNT = 10000 MAX = 906609
993 * 913 と、913 * 993 の２回計算してしまうので、同じ数の組み合わせを省略
Option Explicit
Private cnt: cnt = 0
Private max: max = 0
Call main
WScript.Echo "CNT = " & cnt
WScript.Echo "MAX = " & max
Private Sub main()
Dim i
For i = 999 To 900 Step -1
Dim j
For j = i To 900 Step -1
cnt = cnt + 1
Dim n: n = i * j
Dim s: s = CStr(n)
If s = StrReverse(s) Then
If max < n Then
WScript.Echo CStr(i) & " * " & CStr(j) & " = " & s
max = n
End If
End If
Next
Next
End Sub
D:\study\Project Euler\004>cscript //nologo 004.vbs 993 * 913 = 906609 CNT = 5050 MAX = 906609
最大値以下なら、回文数かどうかのチェックは不要
Option Explicit
Private cnt: cnt = 0
Private max: max = 0
Call main
WScript.Echo "CNT = " & cnt
WScript.Echo "MAX = " & max
Private Sub main()
Dim i
For i = 999 To 900 Step -1
Dim j
For j = i To 900 Step -1
cnt = cnt + 1
Dim n: n = i * j
If n < max Then Exit For
Dim s: s = CStr(n)
If s = StrReverse(s) Then
If max < n Then
WScript.Echo CStr(i) & " * " & CStr(j) & " = " & s
max = n
End If
End If
Next
Next
End Sub
D:\study\Project Euler\004>cscript //nologo 004.vbs 993 * 913 = 906609 CNT = 2385 MAX = 906609
たとえば、現在の最大値が i=993, j=913 の場合、 i≦913 の場合を計算しても仕方ないので
Option Explicit
Private cnt: cnt = 0
Private max: max = 0
Call main
WScript.Echo "CNT = " & cnt
WScript.Echo "MAX = " & max
Private Sub main()
Dim m: m = 0
Dim i
For i = 999 To 900 Step -1
If i = m Then Exit For
Dim j
For j = i To 900 Step -1
cnt = cnt + 1
Dim n: n = i * j
If n < max Then Exit For
Dim s: s = CStr(n)
If s = StrReverse(s) Then
If max < n Then
WScript.Echo CStr(i) & " * " & CStr(j) & " = " & s
max = n
m = j
End If
End If
Next
Next
End Sub
D:\study\Project Euler\004>cscript //nologo 004.vbs 993 * 913 = 906609 CNT = 2371 MAX = 906609
最初の回文数を取得した時点で終了
（結果として正しい解が得られるし、断然速いが、何故これでＯＫなのか説明できない...）
Option Explicit
Private cnt: cnt = 0
Private max: max = 0
Call main
WScript.Echo "CNT = " & cnt
WScript.Echo "MAX = " & max
Private Sub main()
Dim i
For i = 999 To 900 Step -1
Dim j
For j = i To 900 Step -1
cnt = cnt + 1
Dim n: n = i * j
Dim s: s = CStr(n)
If s = StrReverse(s) Then
If max < n Then
WScript.Echo CStr(i) & " * " & CStr(j) & " = " & s
max = n
Exit Sub
End If
End If
Next
Next
End Sub
D:\study\Project Euler\004>cscript //nologo 004.vbs 993 * 913 = 906609 CNT = 687 MAX = 906609
2桁の数の積の場合
| 99 | 98 | 97 | 96 | 95 | 94 | 93 | 92 | 91 | 90 | |
|---|---|---|---|---|---|---|---|---|---|---|
| 99 | 9801 | 9702 | 9603 | 9504 | 9405 | 9306 | 9207 | 9108 | 9009 | 8910 |
| 98 | 9702 | 9604 | 9506 | 9408 | 9310 | 9212 | 9114 | 9016 | 8918 | 8820 |
| 97 | 9603 | 9506 | 9409 | 9312 | 9215 | 9118 | 9021 | 8924 | 8827 | 8730 |
| 96 | 9504 | 9408 | 9312 | 9216 | 9120 | 9024 | 8928 | 8832 | 8736 | 8640 |
| 95 | 9405 | 9310 | 9215 | 9120 | 9025 | 8930 | 8835 | 8740 | 8645 | 8550 |
| 94 | 9306 | 9212 | 9118 | 9024 | 8930 | 8836 | 8742 | 8648 | 8554 | 8460 |
| 93 | 9207 | 9114 | 9021 | 8928 | 8835 | 8742 | 8649 | 8556 | 8463 | 8370 |
| 92 | 9108 | 9016 | 8924 | 8832 | 8740 | 8648 | 8556 | 8464 | 8372 | 8280 |
| 91 | 9009 | 8918 | 8827 | 8736 | 8645 | 8554 | 8463 | 8372 | 8281 | 8190 |
| 90 | 8910 | 8820 | 8730 | 8640 | 8550 | 8460 | 8370 | 8280 | 8190 | 8100 |
大きい数から順に、回文数かどうかチェックするなら、
| 99 | |
|---|---|
| 99 | 9801 |
| 99 | 98 | |
|---|---|---|
| 99 | 9702 | |
| 98 |
| 99 | 98 | 97 | |
|---|---|---|---|
| 99 | 9603 | ||
| 98 | 9604 | ||
| 97 |
| 99 | 98 | 97 | 96 | |
|---|---|---|---|---|
| 99 | 9504 | |||
| 98 | 9506 | |||
| 97 | ||||
| 96 |
の順に計算すべきだが、それだと解を得るまでの計算量が多くなる
| 99 | 98 | 97 | 96 | 95 | 94 | 93 | 92 | 91 | |
|---|---|---|---|---|---|---|---|---|---|
| 99 | 9801 | 9702 | 9603 | 9504 | 9405 | 9306 | 9207 | 9108 | 9009 |
| 98 | 9604 | 9506 | 9408 | 9310 | 9212 | 9114 | 9016 | ||
| 97 | 9409 | 9312 | 9215 | 9118 | 9021 | ||||
| 96 | 9216 | 9120 | 9024 | ||||||
| 95 | 9025 | ||||||||
| 94 | |||||||||
| 93 | |||||||||
| 92 | |||||||||
| 91 |
何故、これだけの計算で解が得られるのか？
| 99 | 98 | 97 | 96 | 95 | 94 | 93 | 92 | 91 | |
|---|---|---|---|---|---|---|---|---|---|
| 99 | 9801 | 9702 | 9603 | 9504 | 9405 | 9306 | 9207 | 9108 | 9009 |
４桁の回文は
で、１１の倍数だから、
Option Explicit
Private loop_cnt: loop_cnt = 0
Private cnt: cnt = 0
Call main
WScript.Echo "ループ回数 = " & CStr(loop_cnt)
WScript.Echo "回文数 判定回数 = " & CStr(cnt)
Private Sub main()
Dim i
For i = 99 To 90 Step -1
Dim x: x = i
Dim y: y = i
Do
loop_cnt = loop_cnt + 1
Dim n: n = x * y
Dim s: s = CStr(n)
WScript.Echo CStr(x) & " * " & CStr(y) & " = " & s
cnt = cnt + 1
If s = StrReverse(s) Then
Exit Sub
End If
x = x + 1
if x > 99 Then Exit Do
y = y - 1
Loop
WScript.Echo ""
x = i
y = i - 1
Do
loop_cnt = loop_cnt + 1
n = x * y
s = CStr(n)
WScript.Echo CStr(x) & " * " & CStr(y) & " = " & s
cnt = cnt + 1
If s = StrReverse(s) Then
Exit Sub
End If
x = x + 1
if x > 99 Then Exit Do
y = y - 1
Loop
WScript.Echo ""
Next
End Sub
D:\Project Euler\Problem 004>cscript //nologo 006.vbs 99 * 99 = 9801 99 * 98 = 9702 98 * 98 = 9604 99 * 97 = 9603 98 * 97 = 9506 99 * 96 = 9504 97 * 97 = 9409 98 * 96 = 9408 99 * 95 = 9405 97 * 96 = 9312 98 * 95 = 9310 99 * 94 = 9306 96 * 96 = 9216 97 * 95 = 9215 98 * 94 = 9212 99 * 93 = 9207 96 * 95 = 9120 97 * 94 = 9118 98 * 93 = 9114 99 * 92 = 9108 95 * 95 = 9025 96 * 94 = 9024 97 * 93 = 9021 98 * 92 = 9016 99 * 91 = 9009 ループ回数 = 25 回文数 判定回数 = 25
のうち、 99 * n 以外のものは、１１の倍数にならないので計算する必要がない。
Option Explicit
Private loop_cnt: loop_cnt = 0
Private cnt: cnt = 0
Call main
WScript.Echo "ループ回数 = " & CStr(loop_cnt)
WScript.Echo "回文数 判定回数 = " & CStr(cnt)
Private Sub main()
Dim i
For i = 99 To 90 Step -1
Dim x: x = i
Dim y: y = i
Do
loop_cnt = loop_cnt + 1
If (x mod 11 = 0) Or (y mod 11 = 0) Then
Dim n: n = x * y
Dim s: s = CStr(n)
WScript.Echo CStr(x) & " * " & CStr(y) & " = " & s
cnt = cnt + 1
If s = StrReverse(s) Then
Exit Sub
End If
End If
x = x + 1
if x > 99 Then Exit Do
y = y - 1
Loop
x = i
y = i - 1
Do
loop_cnt = loop_cnt + 1
If (x mod 11 = 0) Or (y mod 11 = 0) Then
n = x * y
s = CStr(n)
WScript.Echo CStr(x) & " * " & CStr(y) & " = " & s
cnt = cnt + 1
If s = StrReverse(s) Then
Exit Sub
End If
End If
x = x + 1
if x > 99 Then Exit Do
y = y - 1
Loop
Next
End Sub
D:\Project Euler\Problem 004>cscript //nologo 007.vbs 99 * 99 = 9801 99 * 98 = 9702 99 * 97 = 9603 99 * 96 = 9504 99 * 95 = 9405 99 * 94 = 9306 99 * 93 = 9207 99 * 92 = 9108 99 * 91 = 9009 ループ回数 = 25 回文数 判定回数 = 9
同様に６桁の回文も
で、１１の倍数だから
Option Explicit
Private loop_cnt: loop_cnt = 0
Private cnt: cnt = 0
Call main
WScript.Echo "ループ回数 = " & CStr(loop_cnt)
WScript.Echo "回文数 判定回数 = " & CStr(cnt)
Private Sub main()
Dim i
For i = 999 To 900 Step -1
Dim x: x = i
Dim y: y = i
Do
loop_cnt = loop_cnt + 1
If (x mod 11 = 0) Or (y mod 11 = 0) Then
Dim n: n = x * y
Dim s: s = CStr(n)
cnt = cnt + 1
If s = StrReverse(s) Then
WScript.Echo CStr(x) & " * " & CStr(y) & " = " & s
Exit Sub
End If
End If
x = x + 1
if x > 999 Then Exit Do
y = y - 1
Loop
x = i
y = i - 1
Do
loop_cnt = loop_cnt + 1
If (x mod 11 = 0) Or (y mod 11 = 0) Then
n = x * y
s = CStr(n)
cnt = cnt + 1
If s = StrReverse(s) Then
WScript.Echo CStr(x) & " * " & CStr(y) & " = " & s
Exit Sub
End If
End If
x = x + 1
if x > 999 Then Exit Do
y = y - 1
Loop
Next
End Sub
D:\Project Euler\Problem 004>cscript //nologo 008.vbs 993 * 913 = 906609 ループ回数 = 2203 回文数 判定回数 = 352ロジックは一緒だけど、ソースを少し整理した
Option Explicit
Private loop_cnt: loop_cnt = 0
Private cnt: cnt = 0
Call main
WScript.Echo "ループ回数 = " & CStr(loop_cnt)
WScript.Echo "回文数 判定回数 = " & CStr(cnt)
Private Sub main()
Dim i, j
For i = 999 To 100 Step -1
For j = 0 To 1
Dim x: x = i
Dim y: y = i - j
Do
loop_cnt = loop_cnt + 1
If (x mod 11 = 0) Or (y mod 11 = 0) Then
cnt = cnt + 1
Dim s: s = CStr(x * y)
If s = StrReverse(s) Then
WScript.Echo CStr(x) & " * " & CStr(y) & " = " & s
Exit Sub
End If
End If
x = x + 1
y = y - 1
Loop Until (x > 999)
Next
Next
End Sub
D:\Project Euler\Problem 004>cscript //nologo 009.vbs 993 * 913 = 906609 ループ回数 = 2203 回文数 判定回数 = 352
JScript
Perl
PHP
Python
Ruby
PowerShell
Scala
更新日 : 2013.01.11
VBScript版と同様なロジックで実装してみたが、全然 Scala っぽくない...
scala> scala.util.control.Breaks.breakable {
| for (i <- 99 to 10 by -1; j <- 0 to 1) {
| var x = i
| var y = i - j
| do {
| if (x % 11 == 0 || y % 11 == 0 ) {
| var s = (x * y).toString
| if (s == s.reverse) {
| println(x + " * " + y + " = " + s)
| scala.util.control.Breaks.break
| }
| }
| x += 1
| y -= 1
| } while (x <= 99)
| }
| }
99 * 91 = 9009
scala> scala.util.control.Breaks.breakable {
| for (i <- 999 to 100 by -1; j <- 0 to 1) {
| var x = i
| var y = i - j
| do {
| if (x % 11 == 0 || y % 11 == 0 ) {
| var s = (x * y).toString
| if (s == s.reverse) {
| println(x + " * " + y + " = " + s)
| scala.util.control.Breaks.break
| }
| }
| x += 1
| y -= 1
| } while (x <= 999)
| }
| }
993 * 913 = 906609
scala>
更新日 : 2013.01.14
計算量が増えるのには目をつむって、 Scala っぽくしてみる
scala> (1 to 9) res0: scala.collection.immutable.Range.Inclusive with scala.collection.immutable.Range.ByOne = Range(1, 2, 3, 4, 5, 6, 7, 8, 9) scala>
scala> (1 to 9).map(i => (i to 9)) res1: scala.collection.immutable.IndexedSeq[scala.collection.immutable.Range.Inclusive with scala.collection.immutable.Range.ByOne] = Vector(Range(1, 2, 3, 4, 5, 6, 7, 8, 9), Range(2, 3, 4, 5, 6, 7, 8, 9), Range(3, 4, 5, 6, 7, 8, 9), Range(4, 5, 6, 7, 8, 9), Range(5, 6, 7, 8, 9), Range(6, 7, 8, 9), Range(7, 8, 9), Range(8, 9), Range(9)) scala>
scala> (1 to 9).map(i => (i to 9).map(j => (i, j))) res2: scala.collection.immutable.IndexedSeq[scala.collection.immutable.IndexedSeq[(Int, Int)]] = Vector(Vector((1,1), (1,2), (1,3), (1,4), (1,5), (1,6), (1,7), (1,8), (1,9)), Vector((2,2), (2,3), (2,4), (2,5), (2,6), (2,7), (2,8), (2,9)), Vector((3,3), (3,4), (3,5), (3,6), (3,7), (3,8), (3,9)), Vector((4,4), (4,5), (4,6), (4,7), (4,8), (4,9)), Vector((5,5), (5,6), (5,7), (5,8), (5,9)), Vector((6,6), (6,7), (6,8), (6,9)), Vector((7,7), (7,8), (7,9)), Vector((8,8), (8,9)), Vector((9,9))) scala>
scala> (1 to 9).map(i => (i to 9).map(j => (i, j))).flatten res3: scala.collection.immutable.IndexedSeq[(Int, Int)] = Vector((1,1), (1,2), (1,3), (1,4), (1,5), (1,6), (1,7), (1,8), (1,9), (2,2), (2,3), (2,4), (2,5), (2,6), (2,7), (2,8), (2,9), (3,3), (3,4), (3,5), (3,6), (3,7), (3,8), (3,9), (4,4), (4,5), (4,6), (4,7), (4,8), (4,9), (5,5), (5,6), (5,7), (5,8), (5,9), (6,6), (6,7), (6,8), (6,9), (7,7), (7,8), (7,9), (8,8), (8,9), (9,9)) scala>
scala> (1 to 9).map(i => (i to 9).map(j => (i, j))).flatten.filter(t => t._1 % 11 == 0 || t._2 % 11 == 0) res4: scala.collection.immutable.IndexedSeq[(Int, Int)] = Vector() scala>
scala> (10 to 99).map(i => (i to 99).map(j => (i, j))).flatten.filter(t => t._1 % 11 == 0 || t._2 % 11 == 0) res5: scala.collection.immutable.IndexedSeq[(Int, Int)] = Vector((10,11), (10,22), (10,33), (10,44), (10,55), (10,66), (10,77), (10,88), (10,99), (11,11), (11,12), (11,13), (11,14), (11,15), (11,16), (11,17), (11,18), (11,19), (11,20), (11,21), (11,22), (11,23), (11,24), (11,25), (11,26), (11,27), (11,28), (11,29), (11,30), (11,31), (11,32), (11,33), (11,34), (11,35), (11,36), (11,37), (11,38), (11,39), (11,40), (11,41), (11,42), (11,43), (11,44), (11,45), (11,46), (11,47), (11,48), (11,49), (11,50), (11,51), (11,52), (11,53), (11,54), (11,55), (11,56), (11,57), (11,58), (11,59), (11,60), (11,61), (11,62), (11,63), (11,64), (11,65), (11,66), (11,67), (11,68), (11,69), (11,70), (11,71), (11,72), (11,73), (11,74), (11,75), (11,76), (11,77), (11,78), (11,79), (11,80), (11,81), (11,82), (11... scala>
scala> (10 to 99).map(i => (i to 99).map(j => (i, j))).flatten.filter(t => t._1 % 11 == 0 || t._2 % 11 == 0).map(t => t._1 * t._2) res6: scala.collection.immutable.IndexedSeq[Int] = Vector(110, 220, 330, 440, 550, 660, 770, 880, 990, 121, 132, 143, 154, 165, 176, 187, 198, 209, 220, 231, 242, 253, 264, 275, 286, 297, 308, 319, 330, 341, 352, 363, 374, 385, 396, 407, 418, 429, 440, 451, 462, 473, 484, 495, 506, 517, 528, 539, 550, 561, 572, 583, 594, 605, 616, 627, 638, 649, 660, 671, 682, 693, 704, 715, 726, 737, 748, 759, 770, 781, 792, 803, 814, 825, 836, 847, 858, 869, 880, 891, 902, 913, 924, 935, 946, 957, 968, 979, 990, 1001, 1012, 1023, 1034, 1045, 1056, 1067, 1078, 1089, 264, 396, 528, 660, 792, 924, 1056, 1188, 286, 429, 572, 715, 858, 1001, 1144, 1287, 308, 462, 616, 770, 924, 1078, 1232, 1386, 330, 495, 660, 825, 990, 1155, 1320, 1485, 352, 528, 704, 880, 1056, 1232, 1408, 1584, 374, 561, 748, 935, 1122,... scala>
scala> (10 to 99).map(i => (i to 99).map(j => (i, j))).flatten.filter(t => t._1 % 11 == 0 || t._2 % 11 == 0).map(t => t._1 * t._2).max res7: Int = 9801 scala>
scala> (10 to 99).map(i => (i to 99).map(j => (i, j))).flatten.filter(t => t._1 % 11 == 0 || t._2 % 11 == 0).map(t => t._1 * t._2).filter(n => n.toString == n.toString.reverse) res8: scala.collection.immutable.IndexedSeq[Int] = Vector(121, 242, 363, 484, 616, 737, 858, 979, 1001, 858, 1001, 616, 1881, 484, 616, 858, 2002, 2112, 1771, 2112, 858, 2002, 2772, 2552, 2112, 1221, 1551, 1881, 2112, 2442, 2772, 3003, 2992, 2772, 2442, 3663, 3003, 2772, 2112, 2332, 2552, 2772, 2992, 4004, 4224, 4554, 4224, 3773, 4004, 4664, 5005, 5115, 5225, 5335, 5445, 4774, 4224, 6336, 5005, 4554, 4884, 6006, 6336, 6336, 7227, 5775, 6006, 6776, 7007, 8118, 8008, 8448, 9009) scala>
scala> (10 to 99).map(i => (i to 99).map(j => (i, j))).flatten.filter(t => t._1 % 11 == 0 || t._2 % 11 == 0).map(t => t._1 * t._2).filter(n => n.toString == n.toString.reverse).max res9: Int = 9009 scala>
scala> (100 to 999).
| map(i => (i to 999).
| map(j => (i, j))).
| flatten.
| filter(t => t._1 % 11 == 0 || t._2 % 11 == 0).
| map(t => t._1 * t._2).
| filter(n => n.toString == n.toString.reverse).
| max
res10: Int = 906609
scala>
F#
更新日 : 2013.01.15
Scala のロジックを そのまま移植しようとしたが、F# には flatten がない...
> [1..9] - ;; val it : int list = [1; 2; 3; 4; 5; 6; 7; 8; 9]
> [1..9] - |> List.map(fun i -> [i..9]) - ;; val it : int list list = [[1; 2; 3; 4; 5; 6; 7; 8; 9]; [2; 3; 4; 5; 6; 7; 8; 9]; [3; 4; 5; 6; 7; 8; 9]; [4; 5; 6; 7; 8; 9]; [5; 6; 7; 8; 9]; [6; 7; 8; 9]; [7; 8; 9]; [8; 9]; [9]]
> [1..9] - |> List.map(fun i -> [i..9] |> List.map(fun j -> [i; j])) - ;; val it : int list list list = [[[1; 1]; [1; 2]; [1; 3]; [1; 4]; [1; 5]; [1; 6]; [1; 7]; [1; 8]; [1; 9]]; [[2; 2]; [2; 3]; [2; 4]; [2; 5]; [2; 6]; [2; 7]; [2; 8]; [2; 9]]; [[3; 3]; [3; 4]; [3; 5]; [3; 6]; [3; 7]; [3; 8]; [3; 9]]; [[4; 4]; [4; 5]; [4; 6]; [4; 7]; [4; 8]; [4; 9]]; [[5; 5]; [5; 6]; [5; 7]; [5; 8]; [5; 9]]; [[6; 6]; [6; 7]; [6; 8]; [6; 9]]; [[7; 7]; [7; 8]; [7; 9]]; [[8; 8]; [8; 9]]; [[9; 9]]] >
> [1..9] - |> List.map(fun i -> - [i..9] |> List.map(fun j -> (i, j)) - ) - ;; val it : (int * int) list list = [[(1, 1); (1, 2); (1, 3); (1, 4); (1, 5); (1, 6); (1, 7); (1, 8); (1, 9)]; [(2, 2); (2, 3); (2, 4); (2, 5); (2, 6); (2, 7); (2, 8); (2, 9)]; [(3, 3); (3, 4); (3, 5); (3, 6); (3, 7); (3, 8); (3, 9)]; [(4, 4); (4, 5); (4, 6); (4, 7); (4, 8); (4, 9)]; [(5, 5); (5, 6); (5, 7); (5, 8); (5, 9)]; [(6, 6); (6, 7); (6, 8); (6, 9)]; [(7, 7); (7, 8); (7, 9)]; [(8, 8); (8, 9)]; [(9, 9)]]
> [1..9] - |> List.map(fun i -> - [i..9] |> List.map(fun j -> (i, j)) - ) - |> List.map(fun ls -> - ls |> List.map(fun (x, y) -> x * y)) - ;; val it : int list list = [[1; 2; 3; 4; 5; 6; 7; 8; 9]; [4; 6; 8; 10; 12; 14; 16; 18]; [9; 12; 15; 18; 21; 24; 27]; [16; 20; 24; 28; 32; 36]; [25; 30; 35; 40; 45]; [36; 42; 48; 54]; [49; 56; 63]; [64; 72]; [81]]
> [1..9] - |> List.map(fun i -> - [i..9] |> List.map(fun j -> (i, j)) - ) - |> List.map(fun ls -> - ls |> List.map(fun (x, y) -> if (x % 3 = 0 || y % 3 = 0) then x * y else 0) - |> List.map(fun n -> n.ToString "")) - ;; val it : string list list = [["0"; "0"; "3"; "0"; "0"; "6"; "0"; "0"; "9"]; ["0"; "6"; "0"; "0"; "12"; "0"; "0"; "18"]; ["9"; "12"; "15"; "18"; "21"; "24"; "27"]; ["0"; "0"; "24"; "0"; "0"; "36"]; ["0"; "30"; "0"; "0"; "45"]; ["36"; "42"; "48"; "54"]; ["0"; "0"; "63"]; ["0"; "72"]; ["81"]]
> [1..9]
- |> List.map(fun i ->
- [i..9] |> List.map(fun j -> (i, j))
- )
- |> List.map(fun ls ->
- ls |> List.map(fun (x, y) -> if (x % 3 = 0 || y % 3 = 0) then x * y else 0)
- |> List.map(fun n -> n.ToString().ToCharArray() ))
- ;;
val it : char [] list list =
[[[|'0'|]; [|'0'|]; [|'3'|]; [|'0'|]; [|'0'|]; [|'6'|]; [|'0'|]; [|'0'|];
[|'9'|]];
[[|'0'|]; [|'6'|]; [|'0'|]; [|'0'|]; [|'1'; '2'|]; [|'0'|]; [|'0'|];
[|'1'; '8'|]];
[[|'9'|]; [|'1'; '2'|]; [|'1'; '5'|]; [|'1'; '8'|]; [|'2'; '1'|];
[|'2'; '4'|]; [|'2'; '7'|]];
[[|'0'|]; [|'0'|]; [|'2'; '4'|]; [|'0'|]; [|'0'|]; [|'3'; '6'|]];
[[|'0'|]; [|'3'; '0'|]; [|'0'|]; [|'0'|]; [|'4'; '5'|]];
[[|'3'; '6'|]; [|'4'; '2'|]; [|'4'; '8'|]; [|'5'; '4'|]];
[[|'0'|]; [|'0'|]; [|'6'; '3'|]]; [[|'0'|]; [|'7'; '2'|]]; [[|'8'; '1'|]]]
> [1..9]
- |> List.map(fun i ->
- [i..9] |> List.map(fun j -> (i, j))
- )
- |> List.map(fun ls ->
- ls |> List.map(fun (x, y) -> if (x % 3 = 0 || y % 3 = 0) then x * y else 0)
- |> List.map(fun n -> Array.rev(n.ToString().ToCharArray()) ))
- ;;
val it : char [] list list =
[[[|'0'|]; [|'0'|]; [|'3'|]; [|'0'|]; [|'0'|]; [|'6'|]; [|'0'|]; [|'0'|];
[|'9'|]];
[[|'0'|]; [|'6'|]; [|'0'|]; [|'0'|]; [|'2'; '1'|]; [|'0'|]; [|'0'|];
[|'8'; '1'|]];
[[|'9'|]; [|'2'; '1'|]; [|'5'; '1'|]; [|'8'; '1'|]; [|'1'; '2'|];
[|'4'; '2'|]; [|'7'; '2'|]];
[[|'0'|]; [|'0'|]; [|'4'; '2'|]; [|'0'|]; [|'0'|]; [|'6'; '3'|]];
[[|'0'|]; [|'0'; '3'|]; [|'0'|]; [|'0'|]; [|'5'; '4'|]];
[[|'6'; '3'|]; [|'2'; '4'|]; [|'8'; '4'|]; [|'4'; '5'|]];
[[|'0'|]; [|'0'|]; [|'3'; '6'|]]; [[|'0'|]; [|'2'; '7'|]]; [[|'1'; '8'|]]]
> [1..9] - |> List.map(fun i -> - [i..9] |> List.map(fun j -> (i, j)) - ) - |> List.map(fun ls -> - ls |> List.map(fun (x, y) -> if (x % 3 = 0 || y % 3 = 0) then x * y else 0) - |> List.map(fun n -> if Array.rev(n.ToString().ToCharArray()) = n.ToString().ToCharArray() then n else 0)) - ;; val it : int list list = [[0; 0; 3; 0; 0; 6; 0; 0; 9]; [0; 6; 0; 0; 0; 0; 0; 0]; [9; 0; 0; 0; 0; 0; 0]; [0; 0; 0; 0; 0; 0]; [0; 0; 0; 0; 0]; [0; 0; 0; 0]; [0; 0; 0]; [0; 0]; [0]]
> [1..9] - |> List.map(fun i -> - [i..9] |> List.map(fun j -> (i, j)) - ) - |> List.map(fun ls -> - ls |> List.map(fun (x, y) -> if (x % 3 = 0 || y % 3 = 0) then x * y else 0) - |> List.map(fun n -> if Array.rev(n.ToString().ToCharArray()) = n.ToString().ToCharArray() then n else 0) - |> List.max) - ;; val it : int list = [9; 6; 9; 0; 0; 0; 0; 0; 0]
> [1..9] - |> List.map(fun i -> - [i..9] |> List.map(fun j -> (i, j)) - ) - |> List.map(fun ls -> - ls |> List.map(fun (x, y) -> if (x % 3 = 0 || y % 3 = 0) then x * y else 0) - |> List.map(fun n -> if Array.rev(n.ToString().ToCharArray()) = n.ToString().ToCharArray() then n else 0) - |> List.max) - |> List.max - ;; val it : int = 9
> [10..99] - |> List.map(fun i -> - [i..99] |> List.map(fun j -> (i, j)) - ) - |> List.map(fun ls -> - ls |> List.map(fun (x, y) -> if (x % 11 = 0 || y % 11 = 0) then x * y else 0) - |> List.map(fun n -> if Array.rev(n.ToString().ToCharArray()) = n.ToString().ToCharArray() then n else 0) - |> List.max) - |> List.max - ;; val it : int = 9009
> [100..999] - |> List.map(fun i -> - [i..999] |> List.map(fun j -> (i, j)) - ) - |> List.map(fun ls -> - ls |> List.map(fun (x, y) -> if (x % 11 = 0 || y % 11 = 0) then x * y else 0) - |> List.map(fun n -> if Array.rev(n.ToString().ToCharArray()) = n.ToString().ToCharArray() then n else 0) - |> List.max) - |> List.max - ;; val it : int = 906609 >
更新日 : 2013.01.17
いげ太氏から、「Scala で言う flatMap 相当が、F# では collect として定義されていますので、List.collect id で平坦化できますよ。」 とコメントを頂いたので使ってみる。
> [1..9] - |> List.map(fun i -> [i..9] |> List.map(fun j -> (i, j))) - ;; val it : (int * int) list list = [[(1, 1); (1, 2); (1, 3); (1, 4); (1, 5); (1, 6); (1, 7); (1, 8); (1, 9)]; [(2, 2); (2, 3); (2, 4); (2, 5); (2, 6); (2, 7); (2, 8); (2, 9)]; [(3, 3); (3, 4); (3, 5); (3, 6); (3, 7); (3, 8); (3, 9)]; [(4, 4); (4, 5); (4, 6); (4, 7); (4, 8); (4, 9)]; [(5, 5); (5, 6); (5, 7); (5, 8); (5, 9)]; [(6, 6); (6, 7); (6, 8); (6, 9)]; [(7, 7); (7, 8); (7, 9)]; [(8, 8); (8, 9)]; [(9, 9)]]
> - [1..9] - |> List.map(fun i -> [i..9] |> List.map(fun j -> (i, j))) - |> List.collect id - ;; val it : (int * int) list = [(1, 1); (1, 2); (1, 3); (1, 4); (1, 5); (1, 6); (1, 7); (1, 8); (1, 9); (2, 2); (2, 3); (2, 4); (2, 5); (2, 6); (2, 7); (2, 8); (2, 9); (3, 3); (3, 4); (3, 5); (3, 6); (3, 7); (3, 8); (3, 9); (4, 4); (4, 5); (4, 6); (4, 7); (4, 8); (4, 9); (5, 5); (5, 6); (5, 7); (5, 8); (5, 9); (6, 6); (6, 7); (6, 8); (6, 9); (7, 7); (7, 8); (7, 9); (8, 8); (8, 9); (9, 9)]
> - [10..99] - |> List.map(fun i -> [i..99] |> List.map(fun j -> (i, j))) - |> List.collect id - |> List.filter(fun (i, j) -> i % 11 = 0 || j % 11 = 0) - ;; val it : (int * int) list = [(10, 11); (10, 22); (10, 33); (10, 44); (10, 55); (10, 66); (10, 77); (10, 88); (10, 99); (11, 11); (11, 12); (11, 13); (11, 14); (11, 15); (11, 16); (11, 17); (11, 18); (11, 19); (11, 20); (11, 21); (11, 22); (11, 23); (11, 24); (11, 25); (11, 26); (11, 27); (11, 28); (11, 29); (11, 30); (11, 31); (11, 32); (11, 33); (11, 34); (11, 35); (11, 36); (11, 37); (11, 38); (11, 39); (11, 40); (11, 41); (11, 42); (11, 43); (11, 44); (11, 45); (11, 46); (11, 47); (11, 48); (11, 49); (11, 50); (11, 51); (11, 52); (11, 53); (11, 54); (11, 55); (11, 56); (11, 57); (11, 58); (11, 59); (11, 60); (11, 61); (11, 62); (11, 63); (11, 64); (11, 65); (11, 66); (11, 67); (11, 68); (11, 69); (11, 70); (11, 71); (11, 72); (11, 73); (11, 74); (11, 75); (11, 76); (11, 77); (11, 78); (11, 79); (11, 80); (11, 81); (11, 82); (11, 83); (11, 84); (11, 85); (11, 86); (11, 87); (11, 88); (11, 89); (11, 90); (11, 91); (11, 92); (11, 93); (11, 94); (11, 95); (11, 96); (11, 97); (11, 98); (11, 99); (12, 22); (12, 33); ...]
> - [10..99] - |> List.map(fun i -> [i..99] |> List.map(fun j -> (i, j))) - |> List.collect id - |> List.filter(fun (i, j) -> i % 11 = 0 || j % 11 = 0) - |> List.map(fun (i, j) -> i * j) - ;; val it : int list = [110; 220; 330; 440; 550; 660; 770; 880; 990; 121; 132; 143; 154; 165; 176; 187; 198; 209; 220; 231; 242; 253; 264; 275; 286; 297; 308; 319; 330; 341; 352; 363; 374; 385; 396; 407; 418; 429; 440; 451; 462; 473; 484; 495; 506; 517; 528; 539; 550; 561; 572; 583; 594; 605; 616; 627; 638; 649; 660; 671; 682; 693; 704; 715; 726; 737; 748; 759; 770; 781; 792; 803; 814; 825; 836; 847; 858; 869; 880; 891; 902; 913; 924; 935; 946; 957; 968; 979; 990; 1001; 1012; 1023; 1034; 1045; 1056; 1067; 1078; 1089; 264; 396; ...]
> - [10..99] - |> List.map(fun i -> [i..99] |> List.map(fun j -> (i, j))) - |> List.collect id - |> List.filter(fun (i, j) -> i % 11 = 0 || j % 11 = 0) - |> List.map(fun (i, j) -> i * j) - |> List.filter(fun n -> n.ToString().ToCharArray() = Array.rev(n.ToString().ToCharArray())) - ;; val it : int list = [121; 242; 363; 484; 616; 737; 858; 979; 1001; 858; 1001; 616; 1881; 484; 616; 858; 2002; 2112; 1771; 2112; 858; 2002; 2772; 2552; 2112; 1221; 1551; 1881; 2112; 2442; 2772; 3003; 2992; 2772; 2442; 3663; 3003; 2772; 2112; 2332; 2552; 2772; 2992; 4004; 4224; 4554; 4224; 3773; 4004; 4664; 5005; 5115; 5225; 5335; 5445; 4774; 4224; 6336; 5005; 4554; 4884; 6006; 6336; 6336; 7227; 5775; 6006; 6776; 7007; 8118; 8008; 8448; 9009]
> - [10..99] - |> List.map(fun i -> [i..99] |> List.map(fun j -> (i, j))) - |> List.collect id - |> List.filter(fun (i, j) -> i % 11 = 0 || j % 11 = 0) - |> List.map(fun (i, j) -> i * j) - |> List.filter(fun n -> n.ToString().ToCharArray() = Array.rev(n.ToString().ToCharArray())) - |> List.max - ;; val it : int = 9009
> - [100..999] - |> List.map(fun i -> [i..999] |> List.map(fun j -> (i, j))) - |> List.collect id - |> List.filter(fun (i, j) -> i % 11 = 0 || j % 11 = 0) - |> List.map(fun (i, j) -> i * j) - |> List.filter(fun n -> n.ToString().ToCharArray() = Array.rev(n.ToString().ToCharArray())) - |> List.max - ;; val it : int = 906609
VBScript版と同様なロジックでも実装してみる F#には break がないので苦労したが、こちらの記事を参考にさせていただいた。
> exception ForBreak of int;; exception ForBreak of int > try - for i in [99.. -1..10] do - for j in [0..1] do - let mutable x = i - let mutable y = i - j - let mutable f = true - while f do - if (x % 11 = 0 || y % 11 = 0 ) then - let n = x * y - let a = n.ToString().ToCharArray() - if Array.rev(a) = a then - printf "%d * %d = %d\n" x y n - raise (ForBreak 0) - x <- x + 1 - y <- y - 1 - if x > 99 then f <- false - with _ -> () - ;; 99 * 91 = 9009 val it : unit = ()
> try - for i in [999.. -1..100] do - for j in [0..1] do - let mutable x = i - let mutable y = i - j - let mutable f = true - while f do - if (x % 11 = 0 || y % 11 = 0 ) then - let n = x * y - let a = n.ToString().ToCharArray() - if Array.rev(a) = a then - printf "%d * %d = %d\n" x y n - raise (ForBreak 0) - x <- x + 1 - y <- y - 1 - if x > 999 then f <- false - with _ -> () - ;; 993 * 913 = 906609 val it : unit = ()