# Euler Solution 68

(Difference between revisions)
 Revision as of 04:35, 25 April 2009 (view source) (Damn wikimedia putting links in my beau...ugly Haskell code!)← Older edit Latest revision as of 12:14, 1 July 2010 (view source)Althalus (Talk | contribs) (→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]]

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