Last active
March 18, 2017 05:46
-
-
Save murasesyuka/a766113d5c4d8d2cae735063bd5e4060 to your computer and use it in GitHub Desktop.
read chokudai book with F#
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // F# の詳細については、http://fsharp.org を参照してください | |
| // 詳細については、'F# チュートリアル' プロジェクトを参照してください。 | |
| open Microsoft.FSharp.Collections | |
| open System.Collections.Generic | |
| // P. 122 CrazyBot | |
| module CrazyBot = begin | |
| let grid = Array2D.create 100 100 false | |
| let vx = [|1;-1;0; 0|] | |
| let vy = [|0; 0;1;-1|] | |
| let prob = Array.create 4 0.0 | |
| let rec dfs x y n = | |
| if grid.[x,y] then 0.0 | |
| else if n = 0 then 1.0 | |
| else | |
| grid.[x, y] <- true | |
| (* ex.1 | |
| let ret = ref 0.0 | |
| for i = 0 to 3 do | |
| ret := !ret + (dfs (x+vx.[i]) (y+vy.[i]) (n-1)) * prob.[i] | |
| done | |
| *) | |
| //(* ex2 | |
| let mutable ret = 0.0 | |
| for i = 0 to 3 do | |
| ret <- ret + (dfs (x+vx.[i]) (y+vy.[i]) (n-1)) * prob.[i] | |
| //*) | |
| grid.[x, y] <- false | |
| ret | |
| let getProbability (n:int, east:int, west:int, south:int, north:int) = | |
| prob.[0] <- (float)east/100.0 | |
| prob.[1] <- (float)west/100.0 | |
| prob.[2] <- (float)south/100.0 | |
| prob.[3] <- (float)north/100.0 | |
| dfs 50 50 n | |
| end | |
| // P. 130 | |
| module MazeMaker = begin | |
| let longestPath (maze:string [], startRow:int, startCol:int, moveRow:int [], moveCol:int []) = | |
| let mutable now_max = 0 | |
| let width = maze.[0].Length //col | |
| let height = maze.Length //row | |
| let board = Array2D.create height width -1 | |
| board.[startRow, startCol] <- 0 | |
| let queueX = new Queue<int>() | |
| let queueY = new Queue<int>() | |
| queueX.Enqueue(startCol) | |
| queueY.Enqueue(startRow) | |
| while( queueX.Count > 0) do | |
| let x = queueX.Dequeue() | |
| let y = queueY.Dequeue() | |
| let move = List.zip (Array.toList moveCol) (Array.toList moveRow) | |
| //printfn "%A" move | |
| for (mx,my) in move do | |
| let nextX = x + mx | |
| let nextY = y + my | |
| if 0 <= nextX && nextX < width && | |
| 0 <= nextY && nextY < height && | |
| board.[nextY, nextX] = -1 && | |
| maze.[nextY].Substring(nextX,1) = "." then ( | |
| board.[nextY, nextX] <- board.[y,x] + 1; | |
| queueX.Enqueue(nextX); | |
| queueY.Enqueue(nextY); | |
| ) | |
| done | |
| done | |
| // dump board | |
| printfn "%A" board | |
| let mutable fail = false | |
| for i = 0 to height-1 do | |
| for j = 0 to width-1 do | |
| if maze.[i].Substring(j,1) = "." && board.[i,j] = -1 then | |
| fail <- true | |
| now_max <- max now_max board.[i,j] | |
| done | |
| done | |
| if fail then | |
| -1 | |
| else | |
| now_max | |
| end | |
| module NumberMagicEasy = begin | |
| (* purpose : 数字あてゲーム *) | |
| (* theNumber : string -> int *) | |
| let theNumber (answer:string ) = | |
| let check = [| | |
| "YYYY"; | |
| "YYYN"; | |
| "YYNY"; | |
| "YYNN"; | |
| "YNYY"; | |
| "YNYN"; | |
| "YNNY"; | |
| "YNNN"; | |
| "NYYY"; | |
| "NYYN"; | |
| "NYNY"; | |
| "NYNN"; | |
| "NNYY"; | |
| "NNYN"; | |
| "NNNY"; | |
| "NNNN"; | |
| |] | |
| // for i = 0 to check.Length-1 do | |
| // if answer = check.[i] then | |
| // ret <- i+1 | |
| let index = Array.findIndex ((fun ans x -> x = ans ) answer ) check | |
| index + 1 | |
| end | |
| //P. 170 DP | |
| module DP = begin | |
| let h = 5 | |
| let w = 4 | |
| let memo = Array2D.create (h+1) (w+1) 0 | |
| let rec dfs (nowh:int) (noww:int) = | |
| if nowh > h || noww > w then | |
| 0 | |
| elif nowh = h && noww = w then | |
| 1 | |
| else | |
| if memo.[nowh,noww] <> 0 then | |
| memo.[nowh,noww] | |
| else | |
| memo.[nowh,noww] <- (dfs (nowh+1) noww) + (dfs nowh (noww+1)) | |
| memo.[nowh,noww] | |
| let dp = Array2D.create (h+1) (w+1) 0 | |
| let calc = | |
| dp.[0,0] <- 1 | |
| for i = 0 to h do | |
| for j = 0 to w do | |
| if i <> 0 then dp.[i,j] <- dp.[i,j] + dp.[i-1,j] | |
| if j <> 0 then dp.[i,j] <- dp.[i,j] + dp.[i,j-1] | |
| done | |
| //printfn "%A" dp | |
| done | |
| dp.[h,w] | |
| //P.177 | |
| (* weight *) | |
| let ws = [|3;4;1;2;3|] //weight | |
| let ps = [|2;3;2;3;6|] //price | |
| let maxws = 10 | |
| let rec knapsack n w = | |
| //printfn "%d,%d" n w | |
| if w > maxws then -99 // if W>10 then -1 is ans 15. it fail ans? | |
| elif n >= ws.Length then 0 | |
| else | |
| max (knapsack (n+1) w) ((knapsack (n+1) (w+ws.[n])) + ps.[n]) | |
| let knap n w = | |
| let mutable ret = 0 in | |
| let dp = Array2D.create (ws.Length+1) (maxws+1) 0 in //weight ary | |
| for i = 0 to (ws.Length-1) do | |
| for k = 0 to maxws do | |
| //printfn "%A" dp | |
| if ( k + ws.[i]) <= maxws then ( | |
| //printfn "%d, %d = %d" i k dp.[i, k]; | |
| dp.[i+1, k+ws.[i]] <- max dp.[i+1, k+ws.[i]] (dp.[i,k] + ps.[i]); | |
| ret <- (max dp.[i+1, k+ws.[i]] ret) | |
| ) | |
| done | |
| done | |
| ret | |
| end | |
| module CorporationSalary = begin | |
| let mutable salaries = Array.create 50 0 | |
| let rec getSalary i (relations: string []) = | |
| if salaries.[i] = 0 then begin | |
| //printfn "%d" i | |
| let mutable salary = 0 | |
| let relation = relations.[i] | |
| for j = 0 to (relation.Length-1) do | |
| if relation.[j] = 'Y' then | |
| salary <- salary + (getSalary j relations) | |
| if salary = 0 then | |
| salaries.[i] <- 1 | |
| else | |
| salaries.[i] <- salary | |
| end | |
| salaries.[i] | |
| let totalSalary (relations:string []) = | |
| salaries <- Array.create 50 0 | |
| let mutable total = 0 | |
| for i = 0 to relations.Length-1 do | |
| //printfn "%d" i | |
| total <- total + (getSalary i relations) | |
| done | |
| printfn "%d" total | |
| total | |
| end | |
| module BadNeighbors = begin | |
| let maxDonations (donations:int []) = | |
| let mutable ans = 0 | |
| let size = donations.Length | |
| let dp = Array.create size 0 | |
| for i = 0 to size-2 do | |
| dp.[i] <- donations.[i] | |
| if i > 0 then | |
| //printf "%A" dp | |
| dp.[i] <- max dp.[i] dp.[i-1] | |
| if i > 1 then | |
| //printf "%A" dp | |
| dp.[i] <- max dp.[i] (dp.[i-2] + donations.[i]) | |
| ans <- max dp.[i] ans | |
| printfn "%A" dp | |
| done | |
| for i = 0 to size-2 do | |
| dp.[i] <- donations.[i+1] | |
| if i > 0 then | |
| dp.[i] <- max dp.[i] dp.[i-1] | |
| if i > 1 then | |
| dp.[i] <- max dp.[i] (dp.[i-2] + donations.[i+1]) | |
| ans <- max dp.[i] ans | |
| printfn "%A" dp | |
| done | |
| ans | |
| end | |
| module ChessMetric = begin | |
| let howMany (size:int) (first:int []) (last:int []) (numMoves:int) = | |
| let ways = Array3D.create size size (numMoves+1) 0L | |
| let dy = [|-1;0;1;1;1 ; 0;-1;-1; | |
| -1;1; 2; 2; 1;-1;-2;-2|] | |
| let dx = [|1 ;1;1;0;-1;-1;-1; 0; | |
| 2; 2; 1;-1;-2;-2;-1; 1;|] | |
| let ptn_nums = dx.Length-1 | |
| ways.[first.[0], first.[1], 0] <- 1L | |
| for i = 1 to numMoves do | |
| for x in 0..(size-1) do | |
| for y in 0..(size-1) do | |
| for p in 0..ptn_nums do | |
| let ny = y + dy.[p] | |
| let nx = x + dx.[p] | |
| //printfn "%A" ways.[0] | |
| if (ny < 0 || nx < 0 || ny >= size || nx >= size) = false then ( | |
| //printfn "[%2d %2d] n(%d %d) (%d %d) %d" dy.[p] dx.[p] ny nx x y p; | |
| ways.[ny,nx,i] <- ways.[ny,nx,i] + ways.[x,y,i-1]; | |
| ) | |
| done | |
| done | |
| done | |
| done | |
| ways.[last.[0], last.[1], numMoves] | |
| end | |
| [<EntryPoint>] | |
| let main argv = | |
| printfn "hello %A" argv | |
| (* | |
| //crazy bot | |
| printfn "bot %f" (CrazyBot.getProbability (1, 25, 25, 25, 25)) | |
| printfn "bot %f" (CrazyBot.getProbability (2, 25, 25, 25, 25)) | |
| printfn "bot %f" (CrazyBot.getProbability (7, 50, 0, 0, 50)) | |
| printfn "bot %e" (CrazyBot.getProbability (14, 50, 50, 0, 0)) | |
| //*) | |
| (* | |
| printfn "bot %d" | |
| (MazeMaker.longestPath ([| "..."; "..."; "..." |], 0, 1, | |
| [| 1; 0; -1; 0 |], | |
| [| 0; 1; 0; -1 |])) | |
| printfn "bot %d" | |
| (MazeMaker.longestPath ([| "..."; "..."; "..." |], 0, 1, | |
| [| 1; 0; -1; 0; 1; 1; -1; -1 |], | |
| [| 0; 1; 0; -1; 1; -1; 1; -1 |])) | |
| printfn "bot %d" | |
| (MazeMaker.longestPath ([| "x.x"; "..."; "xxx"; "x.x" |], 0, 1, | |
| [| 1; 0; -1; 0 |], | |
| [| 0; 1; 0; -1 |])) | |
| //*) | |
| (* | |
| printfn "num %b" ((NumberMagicEasy.theNumber "YNNN") = 8) | |
| printfn "num %b" ((NumberMagicEasy.theNumber "NNNN") = 16) | |
| printfn "num %b" ((NumberMagicEasy.theNumber "YYYY") = 1) | |
| printfn "num %b" ((NumberMagicEasy.theNumber "NYNY") = 11) | |
| //*) | |
| (* | |
| printfn "dp %d" (DP.dfs 0 0) | |
| printfn "dp %d" (DP.calc) | |
| printfn "knapsack %d" (DP.knapsack 0 0) | |
| printfn "knapsack %d" (DP.knap 0 0) | |
| //*) | |
| (* | |
| printfn "salary %b" (CorporationSalary.totalSalary [|"N"|] = 1) | |
| printfn "salary %b" (CorporationSalary.totalSalary [|"NNNNNN"; | |
| "YNYNNY"; | |
| "YNNNNY"; | |
| "NNNNNN"; | |
| "YNYNNN"; | |
| "YNNYNN"|] = 17 ) | |
| printfn "salary %b" (CorporationSalary.totalSalary [|"NYNNYN"; | |
| "NNNNNN"; | |
| "NNNNNN"; | |
| "NNYNNN"; | |
| "NNNNNN"; | |
| "NNNYYN"|] = 8) | |
| printfn "donation %b" (BadNeighbors.maxDonations [|10;3;2;5;7;8|] = 19) | |
| printfn "donation %b" (BadNeighbors.maxDonations [|11;15|] = 15) | |
| printfn "donation %b" (BadNeighbors.maxDonations [|7;7;7;7;7;7;7|] = 21) | |
| printfn "donation %b" (BadNeighbors.maxDonations [|1;2;3;4;5;1;2;3;4;5|] = 16) | |
| printfn "donation %b" (BadNeighbors.maxDonations [|94;40;49;65;21;21;106;80;92;81;679;4;61; | |
| 6;237;12;72;74;29;95;265;35;47;1;61;397; | |
| 52;72;37;51;1;81;45;435;7;36;57;86;81;72|] = 2926) | |
| //*) | |
| printfn "chessMatrics %b" (ChessMetric.howMany 3 [|0;0|] [|0;1|] 1 = 1L) | |
| printfn "chessMatrics %b" (ChessMetric.howMany 3 [|0;0|] [|1;2|] 1 = 1L) | |
| printfn "chessMatrics %b" (ChessMetric.howMany 3 [|0;0|] [|2;2|] 1 = 0L) | |
| printfn "chessMatrics %b" (ChessMetric.howMany 3 [|0;0|] [|0;0|] 2 = 5L) | |
| printfn "chessMatrics %b" (ChessMetric.howMany 100 [|0;0|] [|0;99|] 50 = 243097320072600L) | |
| 0 // 整数の終了コードします | |
| ; |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment