Euler Solution 68

From ProgSoc Wiki

Jump to: navigation, search

Contents

Solutions for Problem 68

Note: not linked from the main page.

Arrange the numbers 1 to 10 in the following pattern:

        i1
          \
          i2    i4
        /    \ /
      i9     i3
     / \     /
  i10  i7 - i5 - i6
         \
         i8

so that i1 + i2 + i3 = i4 + i3 + i5 = i6 + i5 + i7 = i8 + i7 + i9 = i10 + i9 + i2. Describing this pattern as a string formed by the sets of these numbers, i.e.:

i1 i2 i3 i4 i3 i5 i6 i5 i7 i8 i7 i9 i10 i9 i2

starting with the lowest outer number first. Find the largest such 16 character string.

Pen and Paper by SanguineV

Runtime: maybe 5 minutes

The approach/algorithm:

  1. Know that to have a maximum result you must have the numbers 6-10 on the outside.
  2. Solve the pattern/sums (assumption, there is only one solution)
  3. Make sure that "6" is immediately adjacent to the highest other value in it's line
    1. If not, then redo the pattern with those digits switched (just a permutation/rearrangement)
  4. Turn into a string.

Haskell by SanguineV

Runtime: 965.91 ms

import Data.List

{- Return true if a list of ten integers (ignoring any after the first ten) are a
 - solution to the pattern.
 - Note: ignore all potential solutions with numbers 6-10 on the inside, as these will
 - not solve for 16 digits. -}
sol :: [Integer] -> Bool
sol (i1:i2:i3:i4:i5:i6:i7:i8:i9:i10:is) | i2 > 5 || i3 > 5 || i5 > 5 || i7 > 5 || i9 > 5 = False
sol (i1:i2:i3:i4:i5:i6:i7:i8:i9:i10:is) = foldl (\x y -> x && (r1 == y)) True [r2,r3,r4,r5]
  where
    r1 = i1 + i2 + i3
    r2 = i3 + i4 + i5
    r3 = i5 + i6 + i7
    r4 = i7 + i8 + i9
    r5 = i2 + i9 + i10

{- Return all permutations of a list of things. -}
permute :: [a] -> [ [a] ]
permute [] = [[]]
permute list = concat $ map (\(x:xs) -> map (x:) (permute xs))
                       (take (length list) (unfoldr (\x -> Just (x, tail x ++ [head x])) list))

{- Convert a list of integers into a string that describes their arrangement. -}
toStr :: [Integer] -> String
toStr is = inner (map show is)
  where
    inner (i1:i2:i3:i4:i5:i6:i7:i8:i9:i10:is) = concat [i1,i2,i3,i4,i3,i5,i6,i5,i7,i8,i7,i9,i10,i9,i2]

{- Note that the solution will have to start with a "6" as the minimum outer node, so take
 - the permutations of the other numbers and put "6" as the head of them. Filter out any
 - that do not solve the problem and convert to strings. Discard any strings of length 17.
 - Sort the results and take the last (i.e. largest) one. -}
main = print (last (sort (filter (\l -> length l == 16)
                     (map toStr (filter sol (map (\x -> [6] ++ x)
                                  (permute [1,2,3,4,5,7,8,9,10])))))))


Python by Althalus

Runtime: 28 Seconds.

There are far smarter ways to solve this particular problem, but I didnt put much effort in to it.

ring = [1,2,3,4,5,6,7,8,9,10]
candidates = []

for ring in permutations(ring):
    row1 = sum([ring[0],ring[1],ring[2]])
    row2 = sum([ring[3],ring[2],ring[4]])
    row3 = sum([ring[5],ring[4],ring[6]])
    row4 = sum([ring[7],ring[6],ring[8]])
    row5 = sum([ring[9],ring[8],ring[1]])
    if row1 == row2 and row1 ==  row3 and row1 == row4 and row5 == row1:
        set1 = [ring[0],ring[1],ring[2]]
        set2 = [ring[3],ring[2],ring[4]]
        set3 = [ring[5],ring[4],ring[6]]
        set4 = [ring[7],ring[6],ring[8]]
        set5 = [ring[9],ring[8],ring[1]]
        if ring[0] < min([ring[3],ring[5],ring[7],ring[9]]):
            if ring[0] > 5: print ([set1,set2,set3,set4,set5])
        if ring[3] < min([ring[0],ring[5],ring[7],ring[9]]):
            if ring[3] > 5:  print ([set2,set3,set4,set5,set1])
        if ring[5] < min([ring[3],ring[0],ring[7],ring[9]]):
            if ring[5] > 5: print ([set3,set4,set5,set1,set2])
        if ring[7] < min([ring[3],ring[5],ring[0],ring[9]]):
            if ring[7] > 5: print ([set4,set5,set1,set2,set3])
        if ring[9] < min([ring[3],ring[5],ring[7],ring[0]]):
            if ring[9] > 5: print ([set5,set1,set2,set3,set4])
print time() - start
Personal tools