4
$\begingroup$

project euler 67

When I'm solving this problem, my solution is as following. You can download the data file there.

file = "G:\\Documents\\Mathematica\\MyPE\\51-100\\p067_triangle.txt";

fileImported = 

  Import[file, "Data"] // StringSplit /@ # & // Flatten // ToExpression;

len = Length[fileImported];

partition[list_, pos_] := 

 Module[{}, (pos1 = Prepend[Accumulate@pos, 0];

   res = Take[list, {1, 0} + #] & /@ Partition[pos1, 2, 1])]

numberList1 = partition[fileImported, Range[100]];

numberList1[[1 ;; 4]]

(*
    {{59},{73,41},{52,40,9},{26,53,6,34}}
*)

numberList = MapIndexed[f[#2, #1] &, #] & /@ numberList1;

pickMax[trackList_] := MaximalBy[trackList, Total[#[[All, 2]]] &, 1]

trackUpdate[trackList_] := 

 GroupBy[trackList, Last] // KeySortBy[#, #[[1, 1]] &] & // Values // 

   pickMax /@ # & // Flatten[#, 1] & /@ # &

track[1] = {numberList[[1]]};

track[n_] := Module[{parts, trackAll}, (

   parts = Partition[numberList[[n]], 2, 1];

   (trackAll = 

Map[Flatten, (Thread[#, List, {2}] & /@ 

    Thread[{track[n - 1], parts}]), {2}] // Flatten[#, 1] &);

   (*按节点,聚合路径,按照路径的和,把路径数减少为节点数,比如第三层4条变成3条,47处两条路径共用了一个节点,第四层,6条变成4条。

   Pick the track with largest sum ends up with the same nodes*)

   trackUpdate[trackAll]

   )]

res100 = track[100];

Table[res100[[i, All, 2]] // Total, {i, Length@res100}] // Max;

My question is about the usage of MapIndexed, can it be removed? Here in this way, One can not use a index like that sow in a Do/For loop. and further, along my thread, how can I optimize my codes?

And if we just use numberList1, then in two different positions of one row of the triangle, the numbers may be the same, this will affect the usage of GroupBy in trackUpdate.

$\endgroup$
10
$\begingroup$

It's quite easy once you realize that the bottom-up max sums give you the desired result:

i = Reverse@Import["https://projecteuler.net/project/resources/p067_triangle.txt", "Table"];
f[linPrev_, lin_] := Max /@ (lin + Partition[linPrev, 2, 1])
Fold[f, i]

(* {7273} *)
$\endgroup$
3
  • 1
    $\begingroup$ Import["tri.txt", "Table"] //. {x___, a_, b_} :> {x, a + Max /@ Partition[b, 2, 1]} was my solution about ten years ago. ( Now I feel old. :-( ) $\endgroup$
    – Mr.Wizard
    Aug 23 '16 at 0:16
  • 1
    $\begingroup$ @Mr.Wizard Thanks for posting this and other similarly beautiful solutions in the project euler forum. This solution particularly impressed me, because it's so terse and super fast (unexpectedly fast, as it's base on ReplaceRepeated). $\endgroup$
    – Karsten 7.
    Aug 23 '16 at 5:27
  • $\begingroup$ @Karsten7 I am glad you like this (and others)! Thanks for letting me know. :-) I think I have learned a lot since those days but Project Euler was probably the first time I made a concerted effort to write "nice" code. $\endgroup$
    – Mr.Wizard
    Aug 23 '16 at 7:41
6
$\begingroup$

A top-down approach:

triangle = Import["https://projecteuler.net/project/resources/p067_triangle.txt", "Table"];
listmod[l_List] := {First@l} ~Join~ Partition[l, 2, 1] ~Join~ {Last@l}
mainF[lastList_List, nextList_List] := Max /@ Inner[Plus, listmod[lastList], nextList, List]
Max@Fold[mainF, triangle[[1]], triangle[[2 ;;]]]
7273
$\endgroup$
1
  • $\begingroup$ I've stolen your import format :), Thanks $\endgroup$ Mar 8 '15 at 16:41
2
$\begingroup$
numberListIndexed=partition[Thread[{Range[len],fileImported}],Range[100]];
numberIndexList=#[[All,1]]&/@numberListIndexed;
numberListAsso=AssociationThread[Range[len],fileImported];
pickMax[trackList_]:=MaximalBy[trackList,Total[Map[numberListAsso,#, {1}]]&,1]
append[x_,y_]:=Append[x,#]&/@y
trackExtend[trackList_]:=Block[{len},len=Length@trackList;
Flatten[MapThread[append,{trackList,Partition[numberIndexList[[len+1]],2,1]}],1]]
reduceTrack[trackList_]:=Flatten[Values@GroupBy[trackList,Last,pickMax],1]
trackUpdate[trackList_]:=reduceTrack[trackExtend[trackList]]
trackListAll=Nest[trackUpdate,{{1}},99];
Total/@Map[numberListAsso,trackListAll,{2}]//Max
7273

This is not an efficient solution, but along my first thread I think it's clean and better than the version in question and without use of MapIndexed.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.