Smarmy Pie with Chestnuts

[Changabooniggiwan]

Jack looked sadly at the pastry pie-case before him. With just three measly beans to fill it, his supper would be a dismal affair indeed. What he really craved was a smarmy-pie, filled with goodies. He'd need a potato, a carrot, an onion, a sausage and an egg (along with just one of his beans) to make a sumptuous pie, but alas his pantry was bare and he had no money.

Suddenly, he remembered that today was market day, and, in light of the poor economic climate, the various traders there had agreed to dispense with hard cash and simply trade commodities.

Albert would give a potato in exchange for a bean.
Barney would give an egg in exchange for a potato and a carrot.
Clive would give a potato, carrot and onion in exchange for a sausage.
Derek would give 2 carrots in exchange for a bean.
Ernie would give a sausage and an egg in exchange for a chestnut.
Fred would give 2 beans in exchange for a sausage.
Gordon would give a sausage in exchange for a potato and a carrot.
Harold would give a sausage in exchange for 2 eggs.
Igor would give a chestnut in exchange for a potato, carrot and onion.

Fuelled by hunger, Jack quickly established exactly how to trade his three beans such that he was left with at least one potato, carrot, onion, egg, sausage and bean. That smarmy-pie was now within sight!

Just as he was about to dash to the market, he recalled how a friend had once added a single chestnut to a smarmy-pie, making the dish even more delicious than usual. He reviewed his plan - could he secure at least one of each ingredient including a chestnut?

(1) Find Jack's minimal plan to get the ingredients for a smarmy-pie.

(2) How could Jack adjust his plan to get a smarmy-pie with chestnuts?

[ralphmerridew]

Short version (X = chestnut)
B -> P
PC -> E
S -> PCO
B -> CC
X -> SE
S -> BB
PC -> S
EE -> S
PCO -> X


It's not minimal, but starting from at least two beans, he can get an arbitrary number of any ingredient by using some combination of the below rules:
BB -> BP -> CCP -> CS -> BBC :: (+C)
BB (+C) -> BBC -> BCP -> BS -> BBB :: (+B)
BB (+B) -> BBB -> BBP :: (+P)
BB (+P) -> BBP (+C) -> BBPC -> BBE :: (+E)
BB (+P) -> BBP (+C) -> BBPC -> BBS :: (+S)
BB (+S) -> BBS -> BBPCO :: (+PCO)
BB (+S) -> BBS -> BBPCO -> BBX :: (+X)

[lostdummy]

Nice approach RM - personally I tried mixed combos for optimal solutions but soon I got lost in those ;p

But as you said, it probably is not optimal solution in number of trades ... it adds up to something about 74 trades needed to reach solution (if traders are marked with their starting name letter, than it would be something like: ADGFADGFAGFADGFAGFAADGFAGFAADGFBADGFAGFAADGFGADGFAGFAADGFGCADGFAGFAADGFGCI )

Since I couldn't find easily "optimal" solution manually, I tried quick program, and so far best solution that I got has 25 trades:
(AADGCGCGCGCIECIEFAAHFDIEI)

that solution is with limited 6 trades of same type - so it is possible that some even more optimal solution (ie with less than 25 trades) exists where one type of trade will be used more than 6 times.

*edit* ok, I did search with up to 7 same trade types, and got solution with only 23 trades: (ADGCIECIECHCIECIECHCIEI). When I later managed to check for solution with up to 22 same trades (that was over 50*22^9 ~ 60 trillion operations), no better solution was found, which indicate that no better solution exists - since better one should be in 22 trades ;p