I’ve been ill today, but there’s no better medicine than an easy Project Euler problem! I tried doing some bitwise magic, but in the end my simplest solution proved the fastest as well.
Find the sum of all numbers, less than one million, which are palindromic in base 10 and base 2.
def palindrome? s s == s.reverse end sum = (1..1_000_000).inject(0) do |sum, n| sum += palindrome?(n.to_s) && palindrome?(n.to_s 2) ? n : 0 end puts sum
It’s fugly, but it works. The hardest part was understanding the question. If the longer description didn’t say that there were exactly 4 fractions, I might have gone crazy.
For reals.
Discover all the fractions with an unorthodox cancelling method.
top, bottom = 1, 1 (10..98).each do |i| ((i/10)..9).each do |jt| jt *= 10 (1..9).each do |jo| j = jt + jo next if i >= j if i % 10 == j / 10 && i.to_f / j == (i / 10).to_f / (j % 10) top *= i bottom *= j end end end end puts bottom / bottom.gcd(top)
I recently discovered programmingpraxis.com, and one of the more recent posts dealt with one of the greplin programming challenges. I figured since people were posting their code there, then it wouldn’t be too bad for me to post mine here!
Find the Longest Palindrome in a string:
I doubt this is an optimal solution, but I like how it works:
text = "FourscoreandsevenyearsagoourfaathersbroughtforthonthiscontainentanewnationconceivedinzLibertyanddedicatedtothepropositionthatallmenarecreatedequalNowweareengagedinagreahtcivilwartestingwhetherthatnaptionoranynartionsoconceivedandsodedicatedcanlongendureWeareqmetonagreatbattlefiemldoftzhatwarWehavecometodedicpateaportionofthatfieldasafinalrestingplaceforthosewhoheregavetheirlivesthatthatnationmightliveItisaltogetherfangandproperthatweshoulddothisButinalargersensewecannotdedicatewecannotconsecratewecannothallowthisgroundThebravelmenlivinganddeadwhostruggledherehaveconsecrateditfaraboveourpoorponwertoaddordetractTgheworldadswfilllittlenotlenorlongrememberwhatwesayherebutitcanneverforgetwhattheydidhereItisforusthelivingrathertobededicatedheretotheulnfinishedworkwhichtheywhofoughtherehavethusfarsonoblyadvancedItisratherforustobeherededicatedtothegreattdafskremainingbeforeusthatfromthesehonoreddeadwetakeincreaseddevotiontothatcauseforwhichtheygavethelastpfullmeasureofdevotionthatweherehighlyresolvethatthesedeadshallnothavediedinvainthatthisnationunsderGodshallhaveanewbirthoffreedomandthatgovernmentofthepeoplebythepeopleforthepeopleshallnotperishfromtheearth" def find_longest_palindrome s1, size longest = "" s1.size.times do |start| break if start + size > s1.size s2 = s1[start, size].reverse if s1.include? s2 return s2 end end find_longest_palindrome s1, size - 1 end puts find_longest_palindrome(text, text.length)
I found the site via this post, 10 puzzle websites to sharpen your programming skills. Now that the wedding’s over (pics soon!) I can’t wait to get back to a regular extracurricular programming schedule!
My fiancee’s gone to bed, so I’m bragging to you dear internet.
I just completed The Greplin Programming Challenge! The problems were similar to some of the Project Euler problems I’ve done, but it was still a lot of fun. I can’t wait for the next one!
The End
I did a bit of playing around with wcf, PowerShell and PSUnit the other day.
PSUnit is a unit-testing framework based on NUnit (or should I say JUnit). It was a bit of work to set up but I was really impressed by the speed, robustness, and ISE integration.
It doesn’t make much sense to test application logic through a web service, or even with PowerShell at all, but it’s nice to know there’s such a great tool available. I’ve been having some issues with MSTest and 64 bit assemblies and although I’ll probably end up going with NUnit, it was a fun and educational journey!
Thanks PSUnit Guys!
My solution to this is ugly, but like the tar baby the more I mess with it the worse it gets.
I originally tried to find all the 9 digit pandigitals to cycle through, but was able to cut down the processing by a TON after I figured out that there were only 2 possible digit combinations that could satisfy the problem. (x + xxxx = xxxx and xx + xxx = xxxx)
Enjoy!
Find the sum of all products whose multiplicand/multiplier/product identity can be written as a 1 through 9 pandigital.
def combo size, current = 0, stack = [], results = {}
return results[stack.join.to_i] = stack.clone if size == 0
(1..9).each do |n|
next if stack.include?(n)
stack[current] = n
combo(size - 1, current + 1, stack.clone, results)
end
return results
end
def pandigitals a, b, c
results = []
$repo[a].each_pair do |a_num, a_arr|
$repo[b].each_pair do |b_num, b_arr|
product = a_num * b_num
if $repo[c].include?(product)
c_arr = $repo[c][product]
results.push(product) if (a_arr + b_arr + c_arr).uniq.length == 9
end
end
end
return results
end
$repo = {
1 => combo(1),
2 => combo(2),
3 => combo(3),
4 => combo(4)
}
results = pandigitals(1, 4, 4) + pandigitals(2, 3, 4)
puts results.uniq.inject(:+)
I kept trying to make this problem harder than it actually was, but ultimately a simple greedy solution worked just fine.
I would have saved myself a lot of time by actually solving the problem before attempting to optimize. C’est la vie!
Investigating combinations of English currency denominations.
def count_coins coins, target, last_coin = 0 return 1 if target == 0 total = 0 coins.each do |c| next if c < last_coin total += count_coins(coins, target - c, c) if (target >= c) end total end puts count_coins( [1,2,5,10,20,50,100,200], 200 )
Wrote a quick ruby script that someone might find useful. It will recursively find and list readonly files from a passed in directory. There’s also a an array of file extensions you can exclude.
Nothing Fancy:
require 'find'
# update to exclude by file extension
exclude_extensions = ['.jpg','.txt','.png','.gif','.git']
if(ARGV[0] == nil) then
puts "Please pass in a directory."
exit
end
puts "Searching for NON read only files"
puts "Excluding: " + exclude_extensions.join("s")
writable = []
Find.find(ARGV[0]) do |path|
if File.file?(path) and File.writable?(path) then
if exclude_extensions.include?(File.extname(path))
writable.push path
end
end
end
if writable.size then
puts "Writable Files:"
puts "t" + writable.join("nt")
else
puts "No writable files."
end
I’ve been playing a bit with Silverlight this weekend, and I made a little app based on little game called Flood-It! Unfortunately, at the time I started I couldn’t remember the name of the app, so it’s a bit of an interpretation…
Anyhow, the goal of the game is to ‘flood’ the screen with all one color. It’s a bit difficult to explain, so just click around a bit and it will start making sense.
So far I’ve really liked working in Silverlight, it’s very similar to Flex except that C# blows ActionScript out of the water. I’ve got a few more little projects I’d like to try before I give my final verdict, so don’t touch that dial!
I spent some time playing around with a way to reduce calculations by constructing something akin to a sieve, (2^16 is the same as 4^8 and 16^4), but it turns out that the brute force solutions runs in under a second on my machine so it seemed silly to spend any more time with it.
Ruby even minds the big numbers for me, so the solution is quite trivial:
How many distinct terms are in the sequence generated by a^(b) for 2 ≤ a ≤ 100 and 2 ≤ b ≤ 100?
MIN, MAX = 2,100
values = []
(MIN..MAX).each do |base|
(MIN..MAX).each do |power|
values << base**power
end
end
puts values.uniq.length