Project Euler – Problem 145

The problem: Problem 145

Analysis

Suprisingly enough the brute-force solution works. It takes a couple of minutes but it gets the job done. Suppose we have a function called is_reversible then the following algorithm can be used to count all the reversible numbers below one-billion.

count = 0
for i = 1 upto 1000000000 do
  if (is_reversible(i)) then count++
endfor
output count

Implementation

Uses the OCaml programming language.

(* a left fold over the digits of a positive integer *)
let rec nfoldl f v = function
    0 -> v
  | n -> nfoldl f (f v (n mod 10)) (n / 10)

let reverse = nfoldl (fun n d -> (n * 10) + d) 0

let odd n = n mod 2 = 1
let allodd = nfoldl (fun b d -> b && odd d) true

let is_reversible n =
  n mod 10 <> 0 && allodd (n + reverse n)

let naive_count n =
  let cnt = ref 0 in
    for i = 1 to n-1 do
      if is_reversible i then incr cnt;
    done;
    !cnt

The above code is elegant and it solves the problem but I’m not satisfied with its speed. In that regard I decided to improve on the algorithm a bit.

More Analysis

Notice that since the sum of a number, , and its reverse, must yield a number with all digits odd, it must be the case that cannot begin and end with digits of the same parity (i.e. both even or both odd). Hence, a likely candidate must lie in one of these sets or . Now, , i.e. 200 million. Furthermore, if a number in is reversible then its reverse is in and is obviously reversible as well. This means we only need to generate the elements and count those in that are reversible. Our final answer must then be multiplied by to account for those in .

A Better Implementation

Uses the Haskell programming language. I switched languages when I realised that the list code I needed for this to work was not implemented using tail-recursion in the OCaml standard library. I did rewrite those pieces using tail recursion but in the end I still decided to switch languages just for the fun of it. Actually, the Haskell version below isn’t much better. Its still slow. But very elegant :D. At least I can use it for testing correctness on small cases since the solution is so simple and easy to read.

nfoldl _ v 0 = v
nfoldl f v n = nfoldl f (f v (n `mod` 10)) (n `div` 10)

nreverse = nfoldl (\n d -> (n * 10) + d) 0
allodd = nfoldl (\b d -> b && odd d) True
isReversible n = n `mod` 10 /= 0 && allodd (n + nreverse n)

countDigits = (+1) . floor . logBase 10 . fromIntegral

genCandidates n =
  let gen m i len = if i > len then
                      if m >= n then [] else [m]
                    else
                      if i == 1 then
                        concatMap (\d -> gen (m*10+d) (i+1) len) [1,3,5,7,9]
                      else if i == len then
                        concatMap (\d -> gen (m*10+d) (i+1) len) [2,4,6,8]
                      else
                        concatMap (\d -> gen (m*10+d) (i+1) len) [0..9]
  in concatMap (gen 0 1) [1..countDigits n]

betterCount = (*2) . length . (filter isReversible) . genCandidates

Finally, I bit my tongue and decided to code up a solution in everyone’s favorite system programming language, C.

#include <stdio.h>
#include <math.h>

#define FALSE 0
#define TRUE  1

#define even(n) ((n)%2==0)

int reverse(int n) {
  int m = 0;
  while (n > 0) { m = m*10 + (n%10); n /= 10; }
  return m;
}

int allodd(int n) {
  while (n > 0) {
    if (even(n%10)) return FALSE;
    n /= 10;
  }
  return TRUE;
}

#define is_reversible(n) ((n)%10>0 && allodd((n) + reverse(n)))
#define count_digits(n) ((int)(floor(log10(n) + 1)))

int __count;

void __better_count(int m, int i, int len, int n) {
  int j;
  if (i > len) {
    if (m < n && is_reversible(m)) __count += 2;
  } else {
    if (i == 1) {
      for (j = 1; j <= 9; j+=2) __better_count(m*10+j, i+1, len, n);
    } else if (i == len) {
      for (j = 2; j <= 8; j+=2) __better_count(m*10+j, i+1, len, n);
    } else {
      for (j = 0; j <= 9; j++) __better_count(m*10+j, i+1, len, n);
    }
  }
}

int better_count(int n) {
  int len;
  
  __count = 0;
  for (len = 2; len <= count_digits(n); len++) __better_count(0, 1, len, n);
  return __count;
}

int main(void) {
  printf("%d\n", better_count(1000000000));
  return 0;
}

In the end, the problem was easy and I had a lot of fun playing around with the various languages. I learned quite a lot, so it certainly wasn’t a waste of time.

Project Euler – Problem 71

The problem: Problem 71

Analysis

Let be some integer larger than , and . Let be a function from to defined as follows:

,

where is the largest fraction in that is less than . As the example in the problem illustrates, . We need to find

Let and be an integer between and inclusive. We now define as follows:

,

where is the largest fraction with a denominator of in that is less than .

Clearly then,

.

Thus it suffices to show how to compute . The implementation which will be given below uses a modified binary search to compute . The running time is . Therefore, it takes

time to compute for any .

Implementation of

Uses the racket programming language.

;; finds the largest fraction with a denominator of n
;; that is less than t
(define (p t n) ;; assumes n <= d
  (let ([a (numerator t)]
        [b (denominator t)])
    (/ (let loop ([l 0] [h (- n 1)])
         (if (> l h)
             0
             (let ([m (quotient (+ l h) 2)])
               (if (< (* m b) (* a n))
                   (max m (loop (+ m 1) h))
                   (loop l (- m 1))))))
       n)))

An example showing how to use p to compute .

> (p (/ 3 7) 2)
0
> (p (/ 3 7) 3)
1/3
> (p (/ 3 7) 4)
1/4
> (p (/ 3 7) 5)
2/5
> (p (/ 3 7) 6)
1/3
> (p (/ 3 7) 7)
2/7
> (p (/ 3 7) 8)
3/8

Since is the maximum of the values that were computed, we can conclude that .

Finally, we use the same idea to get . The full implementation takes about 7 seconds to compute the answer.

Tic-tac-toe in Scala – Part 1

What is Tic-tac-toe?

Tic-tac-toe is a two player turn based game played on a 3×3 grid with X and O tokens. Usually X plays first. The objective of the game is to be the first player to place three tokens of the same kind in a row, column or diagonal on the grid.

Here is a game in which the first player, X, wins on column 1 after 7 moves:

An Overview: Architecture

Now that you have been reminded about the game of tic-tac-toe, let me describe to you the design and architecture of the command-line application I wrote to play the game.

The application is composed of three sub-components. The game engine, the computer AI and the command-line interface.

The game engine implements and enforces the rules for the game of tic-tac-toe, i.e. it abstracts and modularizes the game’s logic. This helps to keep the parts of the game that impose the rules completely separate from the interface used to present and interact with the game.

The computer AI sub-component implements three levels of computer intelligence: novice, intermediate and expert.

And finally, the command-line interface is the sub-component that handles the intercommunication between the other two sub-components. It also provides the display and control mechanisms for a human user to view and play the game.

Another Overview: Implementation

I decided to implement the application in the Scala programming language. “Why Scala?”, you may ask. Well, for the simple reason that it is currently the language in which I am trying to become competent and proficient. As a rule, when I’m learning a new language I try to implement some non-trivial programs that will get me to utilize a wide variety of features of the language. Over the years I have found that writing a tic-tac-toe application is one of the best ways for me to accomplish that goal. As I proceed to delve deep into the implementation details of the application in other posts I will try to remember to point out various language features that were convenient or absolutely necessary in order to achieve the particular result I desired.

There are four packages that comprise the application:

1. tt.dwaynecrooks.games.tictactoe – It contains the core classes. Of importance are the Engine, Grid and Token classes.
2. tt.dwaynecrooks.tools.fsm – It contains a set of classes that together implement a simple domain specific language (DSL) for a command driven finite state machine. The Engine class makes full use of the DSL and is a lot more maintainable because of it. This DSL was a joy to implement. The Scala language really made this relatively easy to do.
3. tt.dwaynecrooks.games.tictactoe.ai – It contains the classes that implement the artificial intelligence for the novice, intermediate and expert computer players. There is a Strategy trait that the classes Novice, Intermediate and Expert implement.
4. tt.dwaynecrooks.games.tictactor.cli – It contains the TicTacToe class which implements the command-line interface for the game. The TicTacToe class is also the entry point for the application.

And finally, here is a diagram showing the relationship between the various classes:

The particular way in which the TicTacToe class makes use of the Strategy classes will be discussed when I am explaining the implementation details of the TicTacToe class.

Hopefully at this point you have a general idea of the design, architecture and implementation of the application.

This post has gotten long enough and I am simply getting exhausted explaining all this stuff and drawing all these diagrams. So, in Part 2 I will begin to dig deep into the implementation details. Until then, happy coding.

Notes

• The tic-tac-toe diagram was drawn using the Inkscape Vector Graphics Editor.
• The class diagram was drawn using Dia.