| MoMonkey 的个人资料Monkey Coder日志列表网络 |  工具  帮助 |
|
|
7月30日 The Feniello KeyboardSome years ago (while suffering a little RSI) I learned to touch type on a Dvorak keyboard; difficult to break old habits, but much, much more comfortable feeling. Seriously, I would recommend it! Then a year or so ago I was very bored one day and decided to invent my own keyboard (yes, I am that much of a dork). Beyond ETAOIN SHRDLU I ran a key logger on my dev machine for a couple of weeks and came up with key-pair-timings. For example, after pressing key ‘A’, how long does it take to press key ‘B’; and do that for every combination of keys. Here’s a heat map of exactly that:
Darker red is slower. You can see that after pressing ‘A’ (with my pinky) it’s very slow to follow up with another pinky-key. Quickest by far is to follow up with an opposite-handed home-row key. Well of course! The results were pretty much as expected. For example, here’s after pressing ‘L’:
Look at the L-K pair; very fast; I suspect because you can kind of roll your fingers. Just imagine if T-H-E (the most common English word) was on the L-K-J keys. You could type it almost as a single motion! Optimizing for “the” is not necessarily best though. Optimized For Me I optimized for the sequences of keys that I actually type. Lots of email. Lots of C# and F# code. Lots of technical documentation. I used a simulated annealing type algorithm to come up with a keyboard layout that was optimized for time; given key timings and sequences based on my personal actual usage over two weeks. Here’s the result:
The punctuation keys aren’t placed. The algorithm was coming up with totally bizarre layouts that were just way to hard to use! Notice there are two ‘E’s! One above each middle finger. Genetic algorithms are so strange; coming up with things I would never have thought of! In practice though, I found it actually difficult to use the ‘correct’ E-key while typing; I’d instead favor one or the other regardless of the follow-up key. I’m Not Dork Enough… I don’t actually use the “Feniello” keyboard layout. Some day when I’m bored enough again… What I really use when writing code is:
:-) 7月17日 Rubik's Cube SolverA while back, I had some fun making a Rubik's cube solver in F#. I was planning to make a "pluggable algorithm" mechanism so that I could have it solve using other human-style systems such as Petrus, Fridrich, etc., but right now it just uses a vanilla layer-by-layer system. I've lost interest in this hobby-project so now just posting as is:
The UI
The UI is a bit ugly (nice 3D cube would be good) but works. It's an "unfolded" projection of the cube faces:
You can flip the left, right, up, down, front, and back faces by pressing L, R, U, D, F or B keys respectively and you can rotate the whole cube on it's X, Y or Z axis with those keys or with the arrow keys (X/Y axis only). You can also mix it up with M and reset it with Spacebar.
For example, U R D L produces:
Or, from the reset position, U U D D L L R R F F B B produces the nice pattern:
The real purpose though was to make a solver. Each time you press S, it manipulates the cube a step closer to being solved. The interesting thing (to my anyway) is that the solving algorithm is a single function that takes a single argument of a cube in a particular state and returns a new cube that's been manipulated a bit. The process of solving is just to iterate this function. The only state in the system is the state of the cube being displayed; literally you will see in the code that there is a single cube ref and no other mutables at all.
The Code
The Cube is represented as a 3x3x3 array of Cublets, each of which have an up/down/left/right/front/back Sticker:
#light
open System.Drawing
open System.Windows.Forms
type Sticker = Red | Orange | Yellow | Green | Blue | White
Cublets just have the six stickers and methods for manipulating their orientation:
// The naming conventions for all the transforms (e.g X,
// X2, X', Y, Z, F, U, D, D', L2, etc.)
// come from http://www.cubewhiz.com/notation.html
type Cublet = class
val up : Sticker; val down : Sticker
val left : Sticker; val right : Sticker
val front : Sticker; val back : Sticker
new(u, d, l, r, f, b) = { up = u; down = d; left = l; right = r; front = f; back = b }
new() = { up = Sticker.Red; down = Sticker.Orange;
left = Sticker.Yellow; right = Sticker.White;
front = Sticker.Blue; back = Sticker.Green }
member c.X = new Cublet(c.front, c.back, c.left, c.right, c.down, c.up) // back on X-axis
member c.X2 = c.X.X // 180 on X-axis
member c.X' = c.X2.X // inverse - forward on X-axis (same as back 3)
member c.Y = new Cublet(c.up, c.down, c.front, c.back, c.right, c.left) // left on Y-axis
member c.Y2 = c.Y.Y // 180 on Y-axis
member c.Y' = c.Y2.Y // inverse - right on Y-axis (same as left 3)
member c.Z = c.X.Y.X' // clockwise on Z-axis (same as X, Y, X')
member c.Z2 = c.Z.Z // 180 on Z-axis
member c.Z' = c.Z2.Z // inverse - counter clockwise on Z-axis (same as clockwise 3)
end
Finally, the Cube is a 3x3x3 array of Cublets with methods for manipulating sets of them (rotating slices or changing orientation of the whole cube):
let s = 3 // Cube dimentions
let a = Array3.init s s s
type Cube = class
val cublets : Cublet [,,]
new(c) = { cublets = c }
new() = { cublets = a (fun _ _ _ -> new Cublet()) }
member c.X = new Cube(a (fun x y z -> c.cublets.[x, s - z - 1, y].X)) // back on X-axis
member c.X2 = c.X.X // 180 on X-axis
member c.X' = c.X.X.X // inverse - forward on X-axis (same as back 3)
member c.Y = new Cube(a (fun x y z -> c.cublets.[s - z - 1, y, x].Y)) // left on Y-axis
member c.Y2 = c.Y.Y // 180 on Y-axis
member c.Y' = c.Y2.Y // inverse - right on Y-axis (same as left 3)
member c.Z = c.X.Y.X' // clockwise on Z-axis (same as X, Y, X')
member c.Z2 = c.Z.Z // 180 on Z-axis
member c.Z' = c.Z2.Z // inverse - counter clockwise on Z-axis (same as clockwise 3)
member c.F = new Cube(a (fun x y z -> if z = 0 then c.cublets.[y, s - x - 1, z].Z else c.cublets.[x, y, z]) )
member c.F2 = c.F.F
member c.F' = c.F2.F
member c.B = c.Y2.F.Y2 // everything defined in terms of F, X and Y!
member c.B2 = c.B.B
member c.B' = c.B2.B
member c.L = c.Y'.F.Y
member c.L2 = c.L.L
member c.L' = c.L2.L
member c.R = c.Y.F.Y'
member c.R2 = c.R.R
member c.R' = c.R2.R
member c.U = c.X'.F.X
member c.U2 = c.U.U
member c.U' = c.U2.U
member c.D = c.X.F.X'
member c.D2 = c.D.D
member c.D' = c.D2.D
end
The solver is a giant beast! The cool thing about it is that you just give it a Cube (in any state) and it gives you one back, having done some manipulations. It reports to the console what it's "thinking" as it goes.
Here's a sample solve (showing completion of each phase; it actually took ~80 steps pressing 'S' key):
The code is one giant "solve" function:
[Dang it! Silly MSN Spaces won't let me paste so much in with color highlighting...
 ]let solve (c : Cube) =
let furc = c.cublets.[2, 0, 0].front let ufrc = c.cublets.[2, 0, 0].up let rufc = c.cublets.[2, 0, 0].right let fdrc = c.cublets.[2, 2, 0].front let dfrc = c.cublets.[2, 2, 0].down let rdfc = c.cublets.[2, 2, 0].right let dfe = c.cublets.[1, 2, 0].down let fde = c.cublets.[1, 2, 0].front let dbe = c.cublets.[1, 2, 2].down let dre = c.cublets.[2, 2, 1].down let bde = c.cublets.[1, 2, 2].back let dle = c.cublets.[0, 2, 1].down let ule = c.cublets.[0, 0, 1].up let ure = c.cublets.[2, 0, 1].up let ufe = c.cublets.[1, 0, 0].up let ube = c.cublets.[1, 0, 2].up let ublc = c.cublets.[0, 0, 2].up let ubrc = c.cublets.[2, 0, 2].up let uflc = c.cublets.[0, 0, 0].up let ufrc = c.cublets.[2, 0, 0].up let bulc = c.cublets.[0, 0, 2].back let burc = c.cublets.[2, 0, 2].back let lubc = c.cublets.[0, 0, 2].left let lufc = c.cublets.[0, 0, 0].left let fulc = c.cublets.[0, 0, 0].front let furc = c.cublets.[2, 0, 0].front let rubc = c.cublets.[2, 0, 2].right let rufc = c.cublets.[2, 0, 0].right let fue = c.cublets.[1, 0, 0].front let lue = c.cublets.[0, 0, 1].left let rue = c.cublets.[2, 0, 1].right let bue = c.cublets.[1, 0, 2].back let fs = c.cublets.[1, 1, 0].front let bs = c.cublets.[1, 1, 2].back let ls = c.cublets.[0, 1, 1].left let rs = c.cublets.[2, 1, 1].right let w = Sticker.White let y = Sticker.Yellow let fre_done (c : Cube) = c.cublets.[2, 1, 0].front = c.cublets.[1, 1, 0].front && c.cublets.[2, 1, 0].right = c.cublets.[2, 1, 1].right printfn "------------------------------------------------------------" match c.cublets.[1, 0, 1].up (* up center *), c.cublets.[1, 1, 0].front (*front center *) with | Sticker.Yellow, _ -> // top already yellow printfn "Phase 0: Top is yellow." if // white cross on down-side complete? dfe = w && fde = fs && dbe = w && bde = bs && dle = w && bde = bs && dre = w then printfn "Phase 1: White cross is complete."; let frdc_done (c : Cube) = c.cublets.[2, 2, 0].down = w && c.cublets.[2, 2, 0].front = c.cublets.[1, 1, 0].front && c.cublets.[2, 2, 0].right = c.cublets.[2, 1, 1].right if frdc_done c && frdc_done c.Y && frdc_done c.Y2 && frdc_done c.Y' // corners complete? then printfn "Phase 2: Bottom layer corners are complete."; if fre_done c && fre_done c.Y && fre_done c.Y2 && fre_done c.Y' then printfn "Phase 3: Middle layer edges in place." if ule = y && ure = y && ufe = y && ube = y // yellow cross? then printfn "Phase 4: Yellow cross on top complete." let n = Array.sumByInt (fun c -> if c = y then 1 else 0) [| uflc; ufrc; ublc; ubrc |] if n = 4 then printfn "Phase 5: Yellow top face complete." let bp = bulc = burc let lp = lubc = lufc let fp = fulc = furc let rp = rubc = rufc if bp && lp && fp && rp then printfn "Phase 6: Top corners aligned." if lue = ls && bue = bs && rue = rs && fue = fs // solved?! then printfn "Phase 7: SOLVED!"; c elif lue = lubc then printfn " Move finished edge from left to the back."; c.U elif rue = rubc then printfn " Move finished edge from right to the back."; c.U' elif fue = fulc then printfn " Move finished edge from front to the back."; c.U2 elif fue = rubc then printfn " Move front edge (right) into place."; c.F2.U'.L.R'.F2.L'.R.U'.F2.U2 elif fue = lubc then printfn " Move front edge (left) into place."; c.F2.U.L.R'.F2.L'.R.U.F2.U2 else c elif lp then printfn " Move paired corners from left to the back."; c.Y elif rp then printfn " Move paired corners from right to the back."; c.Y' elif lp then printfn " Move paired corners from front to the back."; c.Y2 else printfn " Permutate top corners."; c.R'.F.R'.B2.R.F'.R'.B2.R2 else // get top yellow face if if n = 0 then printfn " No yellow corners on top." c.cublets.[0, 0, 0].left = y elif n = 1 then printfn " 1 yellow corners on top." c.cublets.[0, 0, 0].up = y elif n = 2 then printfn " 2 yellow corners on top." c.cublets.[0, 0, 0].front = y else failwith "Impossible position!" then printfn " Permutate yellow corders."; c.R.U.R'.U.R.U2.R' else printfn " Rotate yellow corner into position according to corner count."; c.U // get yellow cross elif ule <> y && (ure = y || ufe = y || ube = y) then printfn " Line up top yellow pattern."; c.U else printfn " Permutate yellow edges."; c.F.U.R.U'.R'.F'.U else // get middle layer edges in place if fre_done c then printfn " Middle layer edge in place. Next..."; c.Y elif c.cublets.[2, 1, 0].front = rs && c.cublets.[2, 1, 0].right = fs then printfn " Middle layer edge in place, but flipped wrong."; c.R.U.R'.U'.F'.U'.F.U'.R.U.R'.U'.F'.U'.F elif c.cublets.[2, 0, 0].front = fs && c.cublets.[2, 0, 0].up <> y then printfn " Middle layer edge just nearly in place."; c.U // it will go in next most else printfn " Permutate top and right front edges."; c.R.U.R'.U'.F'.U'.F.U.Y else // get bottom corners in if // corner in place? dfrc = w && fdrc = fs && rdfc = rs then printfn " Down-right corner already in place. Rotate view."; c.Y elif // corner at least lined up vertically? ( // furc lined up? (furc = w || ufrc = w || rufc = w) && // white? (furc = fs || ufrc = fs || rufc = fs) && (furc = rs || ufrc = rs || rufc = rs) // correct corner? ) || ( // fdrc lined up? (fdrc = w || dfrc = w || rdfc = w) && // white? (fdrc = fs || dfrc = fs || rdfc = fs) && (fdrc = rs || dfrc = rs || rdfc = rs) // correct corner? ) then printfn " Slip white corner into place."; c.R.U.R'.U' else printfn " Safely permutate corners."; c.U2.R.U.R'.U'.Y // line up white edges to make cross on down-side elif // white edge lined up with correct right-center? c.cublets.[2, 1, 0].front (* front right edge *) = w && c.cublets.[2, 1, 0].right (* right front edge *) = rs then printfn " Rotate right white edge in."; c.R' // rotate white edge in elif // white edge lined up with correct right-center, but flipped wrong way? c.cublets.[2, 1, 0].front (* front right edge *) = rs && c.cublets.[2, 1, 0].right (* right front edge *) = w then printfn " Rotate flipped right white edge in."; c.D'.F.D // rotate white edge in elif // white edge lined up with correct down-center, but flipped wrong way? c.cublets.[2, 2, 1].right (* right down edge *) = w && c.cublets.[2, 2, 1].down (* down right edge *) = rs then printfn " Rotate flipped down white edge in."; c.R.D'.F.D // rotate white edge in elif // white edge on down side, but wrong one? c.cublets.[2, 2, 1].down (* right down edge *) = w && c.cublets.[2, 2, 1].right (* down right edge *) <> rs // wrong color? then printfn " Rotate wrong down white edge to top."; c.R2.U // rotate white edge out else printfn " Safely permutate edges."; c.R.U.R'.U'.Y // just safely "stir thing up" and continue // look at two faces and flip yellow to up | _, Sticker.Yellow -> printfn " Flip yellow side from front to up."; c.X // front is yellow | _, Sticker.White -> printfn " Flip yellow side from back to up."; c.X' // back must be yellow | Sticker.White, _ -> printfn " Flip yellow side from down to up."; c.X2 // down must be yellow | Sticker.Red, Sticker.Blue | Sticker.Blue, Sticker.Orange | Sticker.Orange, Sticker.Green | Sticker.Green, Sticker.Red -> printfn " Flip yellow side from left to up."; c.Z // left must be yellow | Sticker.Blue, Sticker.Red | Sticker.Red, Sticker.Green | Sticker.Green, Sticker.Orange | Sticker.Orange, Sticker.Blue -> printfn " Flip yellow side from right to up."; c.Z' // right must be yellow | _ -> failwith "Impossible position!" So, finally the UI is very simple; just painting and key wireup:
Looks like a lot of work but really less than 300 lines of code; Fun little toy project! |
|
|
