stuff & things

Problems with Vinagre

So, the default remote desktop app in Ubuntu changed from, um, I don’t know what actually, to a new app called “Vinagre”.

You’d think that’d be something I wouldn’t give a patooty about. The first thing you notice is that it has a list on the side that lets you keep track of servers you connect to which seemed nice enough.

I didn’t use it much at first, so I thought nothing more about it.

Today, I started using it. Dear god:

1. Tried to connect to a fully up-to-date Fedora box (from a fully up-to-date Ubuntu). vino-server crashes on the Fedora machine. I don’t know who’s fault it is, but I don’t really care. Working around that by using XDMCP for the time being, but that’s pretty irritating, interface-wise.
2. While repeatedly trying to connect to the Fedora box (it silently fails on the Ubuntu machine), Vinagre doesn’t save the last-entered machine name, so I have to keep entering “192.168.0….” every time. Irritating.
3. Insanely hard to send Ctrl-Alt-Del to log into Windows machines. For same reason, Ctrl-Alt was chosen as the “Capture/Release” input. So, in order to send Ctrl-Alt-Del to login to a Windows box, you have to first focus the Viagre app (click/whatever), then make sure you’ve uncaptured the input by doing Ctrl-Alt, then finally, recapture the input by doing Ctrl-Alt again, and then without letting go of Ctrl-Alt, press Del to get the final combo. If you just push that combo of course, the Ctrl-Alt first removes capture, and then sends Ctrl-Alt-Del to the local machine. Not very intuitive, especially since there’s very little (no?) indication of whether input is captured.
4. Related, there seems to be absolutely no way to send F11 to the client machine. The general hotkey behaviour is irritating enough as it is: Alt-F4 closes either all of Vinagre, or an app on the client, depending on whether you’ve pressed Ctrl-Alt recently, with no indication of which “mode” you’re in). But, it seems that F11 is even worse. If you’re in captured mode, then most things seem to be sent to the target machien, but apparently F11 was deemed too important to be handled normally, and there’s no configuration mechanism. Fine, until I try to debug something and naturally hit F11 to “Step Into” a function.
5. [Update] When input is captured, there’s no way to scroll the virtual desktop if it’s bigger than your current monitor. WTF?

Basically, it just seems like this app was pushed out way too quick to the main/default user stream. Please give me back my old VNC/RDP viewer. :(

Windows iTunes

I genuinely don’t understand.

I’m not trying to be difficult. I really tried to use iTunes this time. It seemed like the march of inevitability if I wanted to get iPhone apps, and I thought perhaps it would be nice to use. I grabbed the new 7.7 that has iPhone apps, since I wanted to have a look at what was available. It was a little large at 60meg, but hey, whatever, there’s lots of bandwidth to go around these days.

First of all, I had to reboot after installing it. Insane. Strike one. If that was it, well fine. But it’s completely unusably slow on my laptop. The laptop is about 2 years old. It was Dell’s top-of-the-line (XPS M170) when I bought it, so it’s not crazy fast, but it’s not so slow either. I’m pretty sure that it’s still well above the current median machine in performance.

I added my music collection (largely stored on a network drive). It’s about 65 gig, comprised mostly of mp3s and flacs, both ripped from CDs and downloaded. Maybe a little larger than some collections, but certainly not unreasonably large.

I started the “Import” last night around 8pm. It’s now 2pm the next day, and it’s still trying to download album artwork. That’d be fine, except that apparently while it’s doing that, it’s impossible for the UI to be responsive. WTF! Is this goddamn amateur hour? It only refreshes the UI at the end of each attempt to download an album cover?!

Pausing or unpausing music, or changing the volume (since apparently it feels the need to steal the functionality hardware media keys) takes over 10 seconds. That is not hyperbole! It actually takes longer than 10 seconds for anything to happen. On top of that, the mouse event handling also appears to be “sampling” rather than using the event queue properly, because if I just click the play/pause button nothing happens. I have to hold the fucking mouse button down until the UI responds (10 to 15 seconds, remember!), putting the button into the down state, and then release it.

On a side note, iTunes.exe currently owns roughly 300 threads, and has had a continuous IO delta of around 500k/sec for nearly 24 hours now. Jumped up Jesus Christ. You’re not controlling air traffic, you’re cataloging and playing some fucking music.

If this is Apple’s shitty attempt to create some sort of Mac “halo”, they’ve failed miserably. With 100% certainty, I will never, ever, by a Mac with this as the demo of the user experience.

Project Euler, problem #10 in F#

Problem’s quite simply stated this time:

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

Find the sum of all the primes below two million.

First typed in solution was simply:

[2..1999999]
|> Seq.filter(isprime)
|> Seq.fold1(+)

Which got me a number pretty quickly that looked lovely, but was completely wrong. I ran it again, apparently hoping that’d it magically be right the second time. Then I tried for those below 1000000 instead and the sum was negative. Oops! So, the quick fix and working version (changing the “int” range to “bigint” range):

[2I..1999999I]
|> Seq.filter(fun x -> isprime(int x))
|> Seq.fold1(+)

I wonder if there’s a checked-overflow-arithmetic version of F#? Might be useful for some of these questions, since they’re so computationally light anyway.

FSharp Euler #9

The problem statement:

A Pythagorean triplet is a set of three natural numbers, a

a² + b² = c²

For example, 3² + 4² = 9 + 16 = 25 = 5².

There exists exactly one Pythagorean triplet for which a + b + c = 1000.

Find the product abc.

This is another one that’s probably really more “math”-y than programming-y, but I’m enjoying using my new F# hammer to solve these, so might as well keep at it.

It seems like another nice make-a-sequence-and-then-filter-it, but just doing 1..1000 for a, b, and c, results in an awfully big sequence (a billion long). So, a couple simple observations to make the numbers a lot smaller. The main one is that you can just make c = 1000 - a - b, since we know that all answers have to have that form anyway, and then we know a

seq { for a in 1..1000 do
        for b in a..1000 do
            let c = 1000 - a - b
            yield (a,b,c) }
|> Seq.first(fun (a,b,c) -> if a*a + b*b = c*c then Some(a,b,c) else None)

Voila!

Euler #8 in FSharp

The problem:

Find the greatest product of five consecutive digits in the 1000-digit number.

73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450

Treating it as a number is probably not going to be too pleasant.

let prob8num = "7316 ... 52963450"
let chars = prob8num.ToCharArray() |> Array.map(fun x -> Char.code(x) - Char.code('0'))
let rec prob8 (rest : array) =
    if rest.Length     else
        let tl = Array.sub rest 1 (rest.Length - 1)
        let curProd = Array.sub rest 0 5 |> Array.reduce_left( * )
        Math.Max(prob8(tl), curProd)
prob8 chars

So, store it as a string, but then convert it to a character array, and map to the actual numerical values (assuming ASCII I guess).

From that, just a simple recursive solution that does way too much Array.sub’ing. It would make much more sense to use List’s instead of Array’s for all of those .subs, but, there was no sub extraction built into List so I just did it that way instead.

I wrestled a little with the syntax of F# again in this question. I tried putting the “let tl” as inline into the body of the call to Math.Max, but I couldn’t get it to work correctly. Not sure what the required syntax is, maybe I need some of the keywords that I don’t know from non-#light yet?

Also, my copy of Expert F# has arrived, so I’m just starting to peruse it now. Hopefully my code will become more idiomatic soon enough.

And man, do I hate blog software’s handling of code. You’d think that maybe if I typed a less-than sign they could figure out how to escape it moderately properly, but apparently that’s way to complicated. Idiotic.

Project Euler, problem #7 in FSharp

The problem is:

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6^th prime is 13.

What is the 10001^st prime number?

Well, this sort of looks like another one that’s intended more for pencil-and-paper solvers than programming-language solvers. But, maybe prime #10001 is very big, so it becomes a problem for code too. My first thought is just to loop with a counter until we find the 10001st number, but that involves variables which I’m apparently trying to avoid in these problems. I didn’t get to use infinite lists in the last question, so let’s try again:

let rec getprime(n) =
    if n = 1 then 2
    else
        let prev = getprime(n - 1)
        Seq.init_infinite(fun x -> x + prev + 1)
        |> Seq.find(isprime)getprime(10001)

First, we assume we have the previous prime (say it’s “11”). Then, we generate an infinite list starting at the next number (i.e. [12..inf]). Then, find the first number in that list that’s prime, which is the prime after the previous one, which is the one we’re looking for. Finally, take that functionality and wrap it in a recursion stopping at prime #1 = 2 and we’re done.

When I first typed this code in, I messed up the initial value for the start of the sequence as (x + prev), which of course meant it kept finding “2” as the answer. Just a dumb mistake, but the interesting part is that I’d forgotten I even had a debugger since I was getting so used to using FSI to run bits of code. In the end I found the mistake by replacing Seq.find with Seq.nth(0), and adding a couple Console.WriteLine()s.

It’d be really nice if there was a way to put focus onto the FSI tab window though. I find myself defining functions by using Alt-Enter on the body of the function in the text editor, and then wanting to switch to the window to try passing it a few values to see how it works. Without a shortcut, I have to grab the mouse, click in the right place, sometimes Ctrl-End to find the prompt, etc. Maybe I just haven’t found the key yet, not sure.

Euler Project in F#, problem #6

Kick it, Euler:

The sum of the squares of the first ten natural numbers is,

1² + 2² + … + 10² = 385

The square of the sum of the first ten natural numbers is,

(1 + 2 + … + 10)² = 55² = 3025

Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025 − 385 = 2640.

Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

Not much to this one. I learned about the exponentiation operator which seems to be a rewrite to calling a Pow method (it doesn’t seem to work on int). Here’s a “my brain is currently warped into thinking about everything as a sequence and operations on sequences”-solution:

([1.0..100.0] |> Seq.fold (+) 0.0) ** 2.0
- ([1.0..100.0] |> Seq.map(fun x -> x*x) |> Seq.fold(+) 0.0)

See y’all next time.

Euler is streaking in F#, problem #5

Problem #5:

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest number that is evenly divisible by all of the numbers from 1 to 20?

Speaking of infinite sequences, here’s the solution that seemed obvious to me at first.

open Microsoft.FSharp.Math
Seq.init_infinite (fun x -> BigInt.FromInt32 x)
|> Seq.find(fun (x:BigInt) ->
    x > 1I && Seq.for_all (fun (n:BigInt) -> x % n = 0I) [1I..20I])

Nice and simple, just iterate through all numbers, and find the first ne that’s evenly divisible by all the numbers from 1 to 20. Unfortunately let it run for an hour (!) while I had dinner, and it hadn’t completed. I just assumed was doing something dumb, but it seems to give sensible answers for the numbers in the range of 1..10 and 1..16. Apparently, at 1..17 or more though the answer becomes “quite” large. The first version just used int32’s rather than BigInt; I thought perhaps it was getting past 2^32 and so never finding the answer, but it’s hard to say since I wasn’t prepared to wait any longer for the BigInt version to finish.

As a side note, the bigint stuff is a bit ugly in this example, I guess an unfortunate side effect of .NET showing through where the numerical stack is fractured (sensibly and everything, just a little unfortunate here).

In any case, a more mathematical and less brute-force algorithmic approach seems to be required for this problem.

Here’s one that takes only milliseconds to run based on:
http://en.wikipedia.org/wiki/Least_common_multiple#Alternative_method

let rec numTimes(x, p) =
    if x % p = 0 then numTimes(x / p, p) + 1
    else 0
let maxNumTimes p =
    let num = float([1..20] |> Seq.map(fun x -> numTimes(x, p)) |> Seq.fold(max) 0)
    int(Math.Pow(float(p), num))
[1..20]
|> Seq.filter(isprime)
|> Seq.map(maxNumTimes)
|> Seq.fold1( * )

For all primes in the range, figure out the maximum number of times that prime appears in the prime factorization of any of the numbers, and find the product of those primes raised to the maximum number of powers. I learned a little F# in this one, but as far as the math, it would have taken me a long while to recall or figure that out, so it was basically just implementing what Wikipedia described. Oh well.

My “fold” got one better again, instead of passing a pointless anon function and a pointless initial value, last time I got rid of the function. This time I found “fold1” and got rid of the non-useful initial value too! :)

Some more Euler Project, problem #4

This one was pretty straightforward.

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.

Find the largest palindrome made from the product of two 3-digit numbers.

The hardest part was just reversing the number to be able to tell if it was a palindrome. Unfortunately, when I searched for “reverse string f#” I got http://basildoncoder.com/blog/2008/04/21/project-euler-problem-4/ which while certainly a good search result, could have ruined the fun. Anyhow: the solution to reverse (why the heck isn’t there a .Reverse on the .net string anyway?) is the obvious thing. The only thing notable thing here is the “:string” on the argument to the function which is the first time I’ve had to write a type other than the type coercions from float <-> int. It reminds me of the irritating problem with C# generics where it’s often not possible to write the generic function because it has to be completely generic, or has to implement an interface so the type can be where-constrained (or in other words, generics are generics, not templates, I guess. The C++ approach definitely has benefits, sometimes, though.)

let rev (s:string) = new string(Array.rev(s.ToCharArray()))

{ for i in [100..999] do
    for j in [100..999] do
        let x = i * j
        if x.ToString() = rev(x.ToString()) then yield x }
|> Seq.fold(max) 0

After that, it’s pretty simple. I just make a list of all the palindromes created from 3 digit multiplicands, and then fold out the maximum of those. I noticed something very dumb in the last solution, I was folding an anonymous function that just directly passed its arguments to max, which is of course silly. I’m finding F#’s syntax a little weird, but getting better.

It occurs to me after reading Mr. Basildon’s solution that I don’t know the difference between Seq, List, etc. and when it matters. Maybe it’s just that seq can be infinite, vs. List is strictly an actual memory block?