Enigmatic Code

Programming Enigma Puzzles

Enigma 1579: Fifteen

From New Scientist #2744, 23rd January 2010 [link]

In the addition sum above the digits have been replaced by letters and smiley faces. Different letters stand for different digits, the same letter stands for the same digit, a smiley face can be any digit, and leading digits cannot be zero.

If FIVE is divisible by 5 and ELEVEN is divisible by 11, what number is FIFTEEN?

[enigma1579]

Advertisements

6 responses to “Enigma 1579: Fifteen

  1. jimrandell 7 February 2012 at 8:19 pm

    The following Python program runs in 45ms.

    from itertools import permutations
    from enigma import concat
    
    # FIVE is divisible by 5 (hence E is 0 or 5).
    # ELEVEN is divisible by 11 (and can't have a leading 0).
    # Hence E = 5.
    
    E = 5
    
    # consider the FI+IV+VE = TE part of the sum (10^3 10^2)
    # the carry coming in is c2 = 0, 1 or 2
    d1 = set(range(10)).difference((E,))
    for (F, I, V) in permutations(d1, 3):
      if F < 2: continue
    
      TE = 10 * (F + I + V) + (I + V + E)
      (d, r) = divmod(TE, 10)
      c2 = 5 - r
      if not c2 in (0, 1, 2): continue
      (c4, T) = divmod(d, 10)
    
      d2 = d1.difference((F, I, V, T))
      for L in d2:
    
        ELEVE0 = int(concat(E, L, E, V, E)) * 10
        N = 11 - (ELEVE0 % 11)
    
        d3 = d2.difference((N,))
        if len(d3) != 4: continue
    
        # consider the V + E + ? = E column (10^1)
        for c1 in (0, 1, 2, 3):
          if not(0 <= 10*c2 - (V + c1) < 10): continue
    
          # consider the ? + E + ? + ? column (10^0)
          if not(0 <= 10*c1 + N - E < 28): continue
    
          # consider the ? + F + I = F column (10^4)
          for c5 in (0, 1, 2):
            if not(0 <= 10*c5 - (I + c4) < 10): continue
    
            # consider the ? + ? + F = I column (10^5)
            for c6 in (0, 1, 2):
              if not(0 <= (10*c6 + I) - (F + c5) < 19): continue
    
              # consider the ? + ? + ? = F column (10^6)
              if not(2 < F - c6 < 10): continue
    
              print("FIFTEEN={FIFTEEN} FIVE={FIVE} ELEVEN={ELEVEN}".format(FIFTEEN=concat(F, I, F, T, E, E, N), FIVE=concat(F, I, V, E), ELEVEN=ELEVE0+N))
    

    Solution: FIFTEEN = 4043551.

  2. geoffrounce 7 August 2017 at 4:04 pm
    % A Solution in MiniZinc
    
    %                    a
    %        b c d F I V E
    %        e f F I V E g
    %        h F I V E i j
    %        -------------
    %        F I F T E E N
    %        -------------
    
    include "globals.mzn";
     
    var 0..9:F;  var 0..9:I;  var 0..9:V;  var 0..9:E;
    var 0..9:T;  var 0..9:N;  var 0..9:L; 
    
    constraint all_different([F, I, V, E, T, N, L]);  
    
    var 0..9:a;  var 0..9:b;  var 0..9:c; var 0..9:d;
    var 0..9:e;  var 0..9:f;  var 0..9:g; var 0..9:h;
    var 0..9:i;  var 0..9:j;
    
    var 0..3:carry1;  var 0..3:carry2;  var 0..3:carry3; var 0..3:carry4;
    var 0..3:carry5;  var 0..3:carry6;  var 0..3:carry7;
     
    constraint F!= 0 /\ a != 0 /\ b!= 0 /\ e != 0 /\ h != 0;
    
    % Adding columns from right-hand end..
    constraint (a + E + g + j) mod 10 == N /\ (a + E + g + j) div 10 == carry1;
    constraint (V + E + i + carry1) mod 10 == E /\ (V + E + i + carry1) div 10 == carry2;
    constraint (I + V + E + carry2) mod 10 == E /\ (I + V + E + carry2) div 10 == carry3;
    constraint (F + I + V + carry3) mod 10 == T /\ (F + I + V + carry3) div 10 == carry4;
    constraint (d + F + I + carry4) mod 10 == F /\ (d + F + I + carry4) div 10 == carry5;
    constraint (c + f + F + carry5) mod 10 == I /\ (c + f + F + carry5) div 10 == carry6;
    constraint (b + e + h + carry6) == F;
    
    constraint (F*1000 + I*100 + V*10 + E) mod 5 == 0;
    
    constraint (E*100000 + L*10000 + E*1000 + V*100 + E*10 + N) mod 11 == 0;
    
    solve satisfy;
    
    output ["FIFTEEN = " ++ show(F),show(I),show(F),show(T),show(E),show(E),show(N)]
        ++ [",  FIVE = " ++ show(F),show(I),show(V),show(E)]
        ++ [",  ELEVEN = " ++ show(E),show(L),show(E),show(V),show(E),show(N)];
      
    % FIFTEEN = 4043551,  FIVE = 4085,  ELEVEN = 565851
    % Finished in 63msec
    
    
    • hakank 7 August 2017 at 7:12 pm

      @geoffrounce: I’m a curious how you time MiniZinc models since it’s so much faster than when I run them. For you model my fastest machine runs in 122ms. This includes both the flattening to .fzn file and solving.

      Here’s how I time it using Gecode (on a Linux Ubuntu machine) where the model is named test71.mzn:

      $ time minizinc-v --mzn2fzn-cmd "mzn2fzn" -G gecode test71.mzn -f "fzn-gecode -a -mode stat -s true -n 0 "                                     
      

      It is then converted (by minizinc) to these two command:

      $ mzn2fzn -G gecode test71.mzn
      $ mzn-gecode -a -mode stat -s true -n 0  test71.fzn | solns2out test71.ozn
      

      Perhaps you have that fast machine…

      • geoffrounce 7 August 2017 at 8:17 pm

        @hakank: I run the code on a laptop with an I7 64-bit processor and Windows 10 Pro. I run it several times in the MinZinc IDE, mostly with the Geocode bundled solver. Usually the run-time improves and I take the the best time. For most Enigma puzzles I seem to get between 60 and 90 msec with this method.
        @ Jim: Can you say what sort of run-times you get for MiniZinc and by which method?

        • Jim Randell 8 August 2017 at 2:52 pm

          I use the built-in time function of my shell (Z-shell) to measure the run time of a command line. That way I can get a reasonable comparison between different implementations.

          In this case I saved the MiniZinc model to a file and executed it using the mzn-gecode -a solver like this:

          % time mzn-gecode -a enigma1579geoff.mzn                        
          FIFTEEN = 4043551,  FIVE = 4085,  ELEVEN = 565851
          ----------
          ==========
          mzn-gecode -a enigma1579geoff.mzn  0.08s user 0.02s system 112% cpu 0.084 total
          

          I run the command a number of times (usually 16 times for a program that takes less than 1 second), and report the best elapsed time.

          So, according to my methodology, the model Geoff posted (7th August 2017 at 4:04pm) executes in 84ms.

          My timings are done using a 13″ MacBook Pro (Late 2011 model, with a 2.4 GHz Intel Core i5 processor). This is the same laptop I’ve been using since I started Enigmatic Code, so timings should be roughly comparable between my posts (although software has been updated during that time).

  3. hakank 7 August 2017 at 9:05 pm

    @geoffrounce: Thanks. I also usually run it a couple of time and then take some average of the values. By skipping the call to solns2out it saved about 30ms, to 90ms.

Leave a Comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: