# Euler Solution 68

### From ProgSoc Wiki

(Difference between revisions)

(Damn wikimedia putting links in my beau...ugly Haskell code!) |
(→Solutions for Problem 68) |
||

Line 68: | Line 68: | ||

(permute [1,2,3,4,5,7,8,9,10]))))))) | (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 | ||

[[Category: Euler]] | [[Category: Euler]] |

## Latest revision as of 12:14, 1 July 2010

## 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:

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

- 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