Euler Problem 54 asks:

I saw the problem as six tasks:

1. Open the file
2. Populate the hands
3. Populate the cards and assign values
4. Sort the cards to recognize the patterns
5. Score the hands
6. Compare scores and keep a running total for Player 1

I set up a User-defined Type of Card, and then a User-defined Type of Hand, which holds, natually, 5 cards, the string (display) that it came in as, plus a value to compare against the other hand. User-defined Types nicely work with the With…End With syntax construction.

Euler provides the hands as a line of the file containing both hands. I parsed the file into cards, and picked off the cards’ value and suit. I gave a Jack 11, Queen 12, King 13 and Ace 14. I sorted the cards for the purpose of scoring the hand. A Royal Flush got the absolute max of 9. The values went down by 1 until a single high card was zero, with each card of the hand getting evaluated also, to break ties. The most important card’s value was multiplied by 10^-2, the second by 10^-4, the third by 10^-6, the fourth by 10^-8, and the fifth by 10^-10. The most important card is not the highest card, but the one that makes the hand. A King-high straight flush (KQJT9) would score 8.1312111009, while 3 treys plus A2 for three-of-a-kind gets 3.0303031402. Tie breaking is built-in. My dad, who won the rent money back from the landlord playing poker, would have asked how come a Royal Flush (AKQJT and also a straight flush) isn’t 8.1413121110 (could have been) and I’d say, “Well, Dad, it just isn’t.” With that as the scoring system in mind, I passed the hand down the possible fits until it matched, and then set a GoFarther flag to false to stop work, so to speak. Finally, I compared Player One’s hand against Player 2’s, and kept tally.

The lowest possible score is 0.0705040302. That’s the worst hand (75432 of different suits) you can get. In poker, suits only count for flushes, and are never a tie breaker. Tie’s are broken by a highcard comparison, and some ties can be imagined that remain tied down through all the cards (JJ998 for example). When that happenes, the pot is split. You can’t have 4-of-a-kind, 3-of-a-kind, or fullhouse ties. Many a fullboat loses to a higher fullboat’s trio.

It ends up that Euler didn’t include any 5-high straights (Ace as low) but I put it in. The code runs in 46ms on my machine. I used LT for the left angle bracket, and GT for the right angle bracket. It is by far the longest problem by far in lines of code, attested to by many who solved it before, and it was made longer by me in time because I forgot a pattern.

Euler Problem 43 asks:

This problem, over the course of a week, gave me fits. The smallest 0-to-9 pandigital number is 1023456789. The largest is 9876543210. To check every number between them loops 8 billion, 853 million+ times. That’s not doable in “Euler time” of under one minute on a reasonable computer. That’s the “brutest” of brute force approaches, and I knew it was wrong. By inspecting the example case, swapping the 1 and 4 does not change the modulo 2 computation, and swapping the 0 and 6 does not affect the modulo 2 or 3 computations. So, there’s 4 answers there. Turns out there are two more.

It wasn’t until I looked at the problem from inside out that I came up with an approach. The 10th digit has to be whatever is left. The 9th digit has to be whatever is not used in the first 8, and the 8th digit has to be whatever is not used in the first 7, etc. This gave me 10 loops. The following code runs in 20.5 seconds on my MacBookPro running Excel 2002 under Parallels.

Loop L01 only has to go from 1 to 9, since there are no leading zeros. The other 9 loops are from 0 to 9. I thank Steve Bullen for writing the Smart Indenter. There nothing above that speaks elegance to me. Looks brutish in it’s own right. I couldn’t noodle out any special significance to the modulo divisors being the first 7 primes.

…mrt

What to do on a snowy night? No, not that! How about solving Euler Problem 89?

Euler 89 asks:

The tasks are 5:

1. Read the file
2. Parse the Numerals to find the decimal value
3. Rebuild the Numerals in simplest form
4. Apply the complete subtractive rules
5. Use a running total to count keystrokes saved (differences in lengths)

I parsed each numeral from right to left, checking against what was the last operation to determine if the character in question represented an increase or decrease, since the basic rules were followed. Ran in 15 ms. Fast enough. Here’s the code.

Those are all “greater thans” and ampersands. I wanted to use the ROMAN() function, but it breaks a some ridiculously low number like 3999. This one took a while. Version 089B stuffed a spreadsheet as a prototype with the value and the rebuilt number, and then deciphered the rebuild to make sure the going in and going out were the same. It also showed where the subtractive rules as implemented might screw up…and cost key strokes. V089A tried to parse in pairs. Don’t go that way…that’s what ate up the day.

…mrt

Well, congratulate me. I’m now an official Euler blockhead. Technically, I’m a Euler Level 2 Cube, but blockhead seems more appropriate ;-) since a Cube is 50 problems below a Level 3 Novice octohedron.

Euler Problem 52 put me over the top, with 50+ problems solved. Problem 52 asks:

Absolute brute force. Little imagination. Going for that blockhead gusto. 4.9 seconds on my MacBook Pro running Parallels. I got tired of the Mac Excel VBE is a big way. It’s stuck at VBA5, and things like SmartIndenter don’t work there. Anyway, here’s my code:

Here’s my SortString() function, which may show some imagination, and gets used again. It places alphanumerics in order. I use it as above to see if strings have the same content, but in a different order.

No grief about the bubble sort now ;-) . These strings are a dozen or so characters long…

…mrt

Euler Problem 102 asks:

In the above, LTE is “less than or equal”, to outsmart the html bugs.

Any triangle that has all-positive x-coordinates, or all-negative x-coordinates, or similarly all-positive or all-negative y-coordinates, can not contain the origin. A pre-screen will throw all those out. When I first solved this problem, I looked for triangles with both a positive and a negative y-intercept, coupled with both a positive and negative x-intercept, and counted those triangles. That was a successful strategy. LINEST() will return x-intercepts it you swap known-xs and known-ys in the formula. The code looked like this:

It’s right out of the Help for LINEST(), or at least the y-intercept part is. However, after I checked my answer in I read another strategy that was just so flat-out neat that I coded it up. It uses Heron’s Law which calculates the area of a triangle based on a calculation of the semi-perimeter, or 1/2 the sum of the sides: The area of a triangle, given the lengths a,b,c of the sides, is A = sqrt s*(s-a)*(s-b)*(s-c), where s is the semiperimeter 0.5*(a+b+c). If we calculate the area of the suspect triangle, and then the area of the three sub-triangles with a common vertex of the origin, if the sum of the sub-triangle areas equals the area of the whole, then the origin must be within the suspect triangle. That code looked like this:

Those are the escape code for > and < . Can’t figure out how to get it right inside the vb blocks. We can escape it outside, but we truncate if we use the angle brackets, and don’t render the brackets right if we escape. It’s been a conundrum for a while.

I used two functions, TriSides(), which returns the square root of the sum or difference of two squares, so I could do Pythagorean math, and Heron(), which implements Heron’s law:

I admire those who saw the application of Heron going in. One thing that I don’t understand is why I had to convert doubles to singles at the end for the areas to total per Heron. I presume is has to do with the square root routine, but I invite comment. Code ran in one-tenth the time of 102A, at about .01 seconds.

…mrt

Euler Problem 22 asks:

The general task is to time the calculation.
The specific tasks are:

1. Open the file
2. Clean it up (it’s one long line of data, with names wrapped in quotes, and comma-delimited, as in …,”COLIN”,…)
3. Sort the names
4. Determine each name’s alphabetical value
5. Multiply the position by the value
6. Sum the scores

Here is my code:

NameArray is zero-based. Euler’s names aren’t. The first name has position 1. We need to offset by 1.
The alphabetic value is just the sum of the ascii codes (offset by 64, so “A” gets 1) for each letter. This little function does that. It’ll be used in other Euler problems.

This runs in 15 seconds
…mrt

Two problems so far, Eulers 22 and 29, have required sorts, at least for my implementations. Euler 22 sorts over 5000 name strings, and Euler 29 sorts nearly 10,000 numerics. In both cases I used a bubble sort. Bubble sorts get their name from the image of the greater-valued item “bubbling up” to its place in line.

Bubble sorts have some advantages and disadvantages. The BIG disadvantage is that no matter how nearly-sorted the list is at start, you will still go through it (n-1)^2 times, n being the number of items. The advantages of bubble sorts are:

1. They’re easy to code. Typically just nine lines. And
2. To make a descending sort, you reverse just one inequality

To do a bubble sort, you need three things:

1. An indexed list or array with a sortable value or property
2. Explicit or implicit knowledge of the count or quantity of items to sort. You may know the count (n) because you set it, or the computer knows it via Item.count or UBound(Item), for example
3. A TEMP variable of the same type as being sorted, often also called SWAP

If you think of sorting a deck of cards, the outer loop sorts cards from 1 to 51, and the inner loop compares those values with cards from 2 to 52. With fast computers, bubble sorts are probably “fast enough.” Both problems for me took less than 20 seconds.

This is my implementation of a bubble sort. You’ll see it used in the next post, on Euler 22.

…mrt

Euler Problem 19 asks:

Wow. First thought: Euler actually got the century right. Math-minded indeed. Second thought: I need a day counter, a week counter, a month counter, a leap year checker. That’s a lot of conditionals. No wonder this is here. Third thought: I’m doing this in Excel. Piece of cake. This may be the only one aimed right at us, if not intentionally. Here’s my code. Ran in under a second.

Coded it up. It ran the first time, and I checked in with the right answer. I was feeling so good until I saw the pencil and paper approach of those who’d solved it …100 years with 12 months per year over 7 days

…mrt