# Programmers: a bit of code golf?

**URL:** <https://boards.straightdope.com/t/programmers-a-bit-of-code-golf/584245>\
**Category:** The Game Room\
**Created:** [June 3, 2011, 9:24pm UTC](https://boards.straightdope.com/t/programmers-a-bit-of-code-golf/584245 "2011-06-03T21:24:56Z")\
**Posts on this page:** 20\
**Page:** 5

<div class="post-metadata">

**Author:** ![Indistinguishable](https://avatars.discourse-cdn.com/v4/letter/i/90ced4/32.png) [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)\
**Post date:** [June 14, 2011, 10:14pm UTC](https://boards.straightdope.com/t/programmers-a-bit-of-code-golf/584245/81 "2011-06-14T22:14:39Z")

</div>

> [@septimus](#):
>
> Neat, huh?

The thread’s moved on, but I wanted to say: Yeah, that’s neat.

---

<div class="post-metadata">

**Author:** ![Sage\_Rat](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/sage_rat/32/399_2.png) [@Sage\_Rat](https://boards.straightdope.com/u/Sage_Rat)\
**Post date:** [June 15, 2011, 6:10am UTC](https://boards.straightdope.com/t/programmers-a-bit-of-code-golf/584245/82 "2011-06-15T06:10:04Z")

</div>

This is, effectively, the same solution as **septimus** gives (in the D language):

```auto

import std.stdio;

template NickelNDime(uint target) {
	void result(ref ulong total, uint currentValue = 0) {
		uint testValue = currentValue + 1;
		if (testValue == target) ++total;
		else if (testValue < target) {
			result(total, testValue);
		
			testValue = currentValue + 5;
			if (testValue == target) ++total;
			else if (testValue < target) {
				result(total, testValue);
			
				testValue = currentValue + 10;
				if (testValue == target) ++total;
				else if (testValue < target) result(total, testValue);
			}
		}
	}
}

int main(string[] args) {
	ulong total = 0;
	NickelNDime!(100).result(total);
	writefln("Result: %s", total);
	
	return 0;
}

```

I gave up waiting for it to complete, but do get the correct answer for 25. I’d be interested in optimizing it – directly stacking instead of using the function stack, and splitting it into threads – but left it as is for the sake of keeping the code clear.

The task I would give, should anyone want to try it:

You are given a bundle of nodes. Each node has a list of nodes that it is connected to and a cost to travel to that node. There are no orphaned nodes, but any one node is only connected to a subset of all nodes. Create a method that accepts two nodes, an origin and a destination, and returns the cheapest path.

```auto

struct Node {
	Node others[];	// guaranteed to be the same length as cost[]
	uint cost[];	// guaranteed to be the same length as others[]
	// any variables you want to add
}

Node[] cheapestPath(Node origin, Node destination);

```

---

<div class="post-metadata">

**Author:** ![septimus](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/septimus/32/410_2.png) [@septimus](https://boards.straightdope.com/u/septimus)\
**Post date:** [June 15, 2011, 7:25am UTC](https://boards.straightdope.com/t/programmers-a-bit-of-code-golf/584245/83 "2011-06-15T07:25:28Z")

</div>

> [@Sage\_Rat](#):
>
> You are given a bundle of nodes. Each node has a list of nodes that it is connected to and a cost to travel to that node. There are no orphaned nodes, but any one node is only connected to a subset of all nodes. Create a method that accepts two nodes, an origin and a destination, and returns the cheapest path.
> 
> ```
> // any variables you want to add
> 
> ```

Just to nitpick: Costs must be stipulated to be non-negative, as otherwise winning strategy is to find a loop of negative cost and spin around it for a while! 😃

---

<div class="post-metadata">

**Author:** ![Sage\_Rat](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/sage_rat/32/399_2.png) [@Sage\_Rat](https://boards.straightdope.com/u/Sage_Rat)\
**Post date:** [June 15, 2011, 7:38am UTC](https://boards.straightdope.com/t/programmers-a-bit-of-code-golf/584245/84 "2011-06-15T07:38:16Z")

</div>

> [@septimus](#):
>
> Just to nitpick: Costs must be stipulated to be non-negative, as otherwise winning strategy is to find a loop of negative cost and spin around it for a while! 😃

They are an unsigned int in my example, and should be presumed to be a minimum of 1.

---

<div class="post-metadata">

**Author:** ![Lance\_Turbo](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/lance_turbo/32/6156_2.png) [@Lance\_Turbo](https://boards.straightdope.com/u/Lance_Turbo)\
**Post date:** [June 15, 2011, 8:46am UTC](https://boards.straightdope.com/t/programmers-a-bit-of-code-golf/584245/85 "2011-06-15T08:46:52Z")

</div>

> [@Sage\_Rat](#):
>
> I gave up waiting for it to complete, but do get the correct answer for 25. I’d be interested in optimizing it – directly stacking instead of using the function stack, and splitting it into threads – but left it as is for the sake of keeping the code clear.

It’s a straight forward linear recurrence so you should be able to compute it in under a second using memoization or something similar.

---

<div class="post-metadata">

**Author:** ![Indistinguishable](https://avatars.discourse-cdn.com/v4/letter/i/90ced4/32.png) [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)\
**Post date:** [June 15, 2011, 9:55am UTC](https://boards.straightdope.com/t/programmers-a-bit-of-code-golf/584245/86 "2011-06-15T09:55:12Z")

</div>

Yeah, the problem with **Sage Rat** ’s code, from an efficiency standpoint, is just the lack of memoization.

Anyway, I tackled the cheapest path problem, straightforwardly using Dijkstra’s algorithm:

```auto

data Distance a = Finite a | Infinite

distComp (Finite a) (Finite b) = compare a b
distComp (Finite _) Infinite = LT
distComp Infinite (Finite _) = GT
distComp Infinite Infinite = EQ

distAdd (Finite a) (Finite b) = Finite (a + b)
distAdd _ _ = Infinite

dijkstra nodes node_eq metric source dest
 = reverse $ fst $ dijkstra_helper source (node_eq source)
   (
 -> if node_eq source n then ([], Finite 0) else ([n], metric source n))
   where dijkstra_helper current visited path = if visited dest then path dest
         else let (pcurr, dcurr) = path current
                  path' = memo $ 
                          
 -> minimumBy (\(_, d1) (_, d2) -> distComp d1 d2)
                          [path n, (n:pcurr, distAdd (metric current n) dcurr)]
                  dist' = snd . path'
                  current' = minimumBy (\a b -> distComp (dist' a) (dist' b))
                             (filter (not . visited) nodes)
                  visited' n = node_eq current' n || visited n
              in dijkstra_helper current' visited' path'
         memo f = let l = [(n, f n) | n <- nodes]
                  in 
 -> head [fn | (n', fn) <- l, node_eq n n']

dijkstra_marshall nodes node_eq node_neighbors source dest
 = dijkstra nodes node_eq metric source dest
   where metric n1 n2 = if node_eq n1 n2 then Finite 0
         else case [d | (n2', d) <- node_neighbors n1, node_eq n2 n2'] of 
              (d:_) -> Finite d; [] -> Infinite

```

dijkstra does all the work; its arguments are a list of nodes, a function comparing nodes for equality, a function taking in two nodes and returning the distance from the first to the second (possibly infinite), a source node, and a destination node; it returns the shortest path from the source to the destination (specified as a list of nodes in order, not including the source but including the destination).

dijkstra\_marshall is a wrapper for dijkstra where the argument giving the distance between two nodes is replaced with a function sending any node to a list of pairs of its neighbor nodes and the distances to them

---

<div class="post-metadata">

**Author:** ![Indistinguishable](https://avatars.discourse-cdn.com/v4/letter/i/90ced4/32.png) [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)\
**Post date:** [June 15, 2011, 10:09am UTC](https://boards.straightdope.com/t/programmers-a-bit-of-code-golf/584245/87 "2011-06-15T10:09:22Z")

</div>

For verification of correctness, here’s an undirected graph example (taken from the graphic on Wikipedia’s article for Dijkstra’s algorithm):

```auto

nodes = [0..5]
node_eq = (==)
neigh 0 = [(1, 9), (3, 6)]
neigh 1 = [(0, 9), (2, 2), (4, 14)]
neigh 2 = [(1, 2), (3, 11), (4, 9), (5, 10)]
neigh 3 = [(0, 6), (2, 11), (5, 15)]
neigh 4 = [(1, 14), (2, 9), (5, 7)]
neigh 5 = [(2, 10), (3, 15), (4, 7)]
shortestPaths = [(a, b, dijkstra_marshall nodes node_eq neigh a b) | a <- nodes, b <- nodes]

```

[Of course, actually computing shortestPaths this way would be wasteful, since it restarts Dijkstra’s algorithm from scratch each time the destination node is changed even if the source node remains the same… It’s just a correctness test of the single-use code above]

Anyway, shortestPaths evaluates to [(0,0,),(0,1,[1]),(0,2,[1,2]),(0,3,[3]),(0,4,[1,2,4]),(0,5,[3,5]),(1,0,[0]),(1,1,),(1,2,[2]),(1,3,[2,3]),(1,4,[2,4]),(1,5,[2,5]),(2,0,[1,0]),(2,1,[1]),(2,2,),(2,3,[3]),(2,4,[4]),(2,5,[5]),(3,0,[0]),(3,1,[2,1]),(3,2,[2]),(3,3,),(3,4,[2,4]),(3,5,[5]),(4,0,[2,1,0]),(4,1,[2,1]),(4,2,[2]),(4,3,[2,3]),(4,4,),(4,5,[5]),(5,0,[2,1,0]),(5,1,[2,1]),(5,2,[2]),(5,3,[3]),(5,4,[4]),(5,5,)], which seems to me correct.

And here’s a directed graph example (taken from this [random graphic](http://stochastix.files.wordpress.com/2009/07/iou-graph-10-nodes-and-20-edges.png) I found on the web):

```auto

nodes = [1..10]
node_eq = (==)
neigh 1 = [(2, 10), (4, 20), (5, 20), (6, 5), (7, 15)]
neigh 2 = [(3, 5), (4, 10)]
neigh 3 = [(2, 15), (4, 5)]
neigh 4 = [(5, 10)]
neigh 5 = [(6, 5)]
neigh 6 = []
neigh 7 = [(6, 10)]
neigh 8 = [(1, 5), (2, 20), (7, 5)]
neigh 9 = [(2, 15), (8, 20), (10, 10)]
neigh 10 = [(2, 5), (3, 15)]
shortestPaths = [(a, b, dijkstra_marshall nodes node_eq neigh a b) | a <- nodes, b <- nodes]

```

shortestPaths evaluates to [(1,1,),(1,2,[2]),(1,3,[2,3]),(1,4,[4]),(1,5,[5]),(1,6,[6]),(1,7,[7]),(1,8,[8]),(1,9,[9]),(1,10,[10]),(2,1,[1]),(2,2,),(2,3,[3]),(2,4,[4]),(2,5,[4,5]),(2,6,[4,5,6]),(2,7,[7]),(2,8,[8]),(2,9,[9]),(2,10,[10]),(3,1,[1]),(3,2,[2]),(3,3,),(3,4,[4]),(3,5,[4,5]),(3,6,[4,5,6]),(3,7,[7]),(3,8,[8]),(3,9,[9]),(3,10,[10]),(4,1,[1]),(4,2,[2]),(4,3,[3]),(4,4,),(4,5,[5]),(4,6,[5,6]),(4,7,[7]),(4,8,[8]),(4,9,[9]),(4,10,[10]),(5,1,[1]),(5,2,[2]),(5,3,[3]),(5,4,[4]),(5,5,),(5,6,[6]),(5,7,[7]),(5,8,[8]),(5,9,[9]),(5,10,[10]),(6,1,[1]),(6,2,[2]),(6,3,[3]),(6,4,[4]),(6,5,[5]),(6,6,),(6,7,[7]),(6,8,[8]),(6,9,[9]),(6,10,[10]),(7,1,[1]),(7,2,[2]),(7,3,[3]),(7,4,[4]),(7,5,[5]),(7,6,[6]),(7,7,),(7,8,[8]),(7,9,[9]),(7,10,[10]),(8,1,[1]),(8,2,[1,2]),(8,3,[1,2,3]),(8,4,[1,4]),(8,5,[1,5]),(8,6,[1,6]),(8,7,[7]),(8,8,),(8,9,[9]),(8,10,[10]),(9,1,[8,1]),(9,2,[2]),(9,3,[2,3]),(9,4,[2,4]),(9,5,[2,4,5]),(9,6,[8,1,6]),(9,7,[8,7]),(9,8,[8]),(9,9,),(9,10,[10]),(10,1,[1]),(10,2,[2]),(10,3,[2,3]),(10,4,[2,4]),(10,5,[2,4,5]),(10,6,[2,4,5,6]),(10,7,[7]),(10,8,[8]),(10,9,[9]),(10,10,)]. If you spot an error in there, let me know. (Probably not the best graph to test on, but I’m lazy…)

Also, for pedantry’s sake, I said above “(specified as a list of nodes in order, not including the source but including the destination)”, but should actually have noted that the destination is only included if it is distinct from the source (i.e., what is output is the ordered list of nodes which are traversed after the source)…

---

<div class="post-metadata">

**Author:** ![Sage\_Rat](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/sage_rat/32/399_2.png) [@Sage\_Rat](https://boards.straightdope.com/u/Sage_Rat)\
**Post date:** [June 15, 2011, 10:14am UTC](https://boards.straightdope.com/t/programmers-a-bit-of-code-golf/584245/88 "2011-06-15T10:14:45Z")

</div>

> [@Lance\_Turbo](#):
>
> It’s a straight forward linear recurrence so you should be able to compute it in under a second using memoization or something similar.

Ah, I thought **septimus** was partially controlling his own stack, but I think I have an inkling of what he’s actually doing. I’ll have to study it when I’m more awake to be able to internalize it.

---

<div class="post-metadata">

**Author:** ![Indistinguishable](https://avatars.discourse-cdn.com/v4/letter/i/90ced4/32.png) [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)\
**Post date:** [June 15, 2011, 10:21am UTC](https://boards.straightdope.com/t/programmers-a-bit-of-code-golf/584245/89 "2011-06-15T10:21:34Z")

</div>

> [@Indistinguishable](#):
>
> ```auto
> 
> where metric n1 n2 = if node_eq n1 n2 then Finite 0
> 
> ```

It occurs to me I had no good reason for this insertion of 0-length self-loops at every node…

Oh well, one wasted line.

---

<div class="post-metadata">

**Author:** ![Lance\_Turbo](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/lance_turbo/32/6156_2.png) [@Lance\_Turbo](https://boards.straightdope.com/u/Lance_Turbo)\
**Post date:** [June 15, 2011, 10:26am UTC](https://boards.straightdope.com/t/programmers-a-bit-of-code-golf/584245/90 "2011-06-15T10:26:39Z")

</div>

I was going to tackle the path problem but there’s no point now. But my solution is kind of neat, so I’ll sketch it out.

Given n nodes create an n x n matrix, A, where the entry in i, j is x^w where w is the weight of the edge between nodes i and j. Enter 0 in the i, j spot if nodes i and j are not connected. Compute M = A + A^2 + … + A^(n-1). The entry in the i, j spot of M is a polynomial and the exponent of its lowest degree term is the minimum weight of a path between nodes i and j.

This is not as efficient as Djikstra, but we have calculated a lot more, including the min weight path between any pair of nodes, and the number of distinct paths that have that weight.

---

<div class="post-metadata">

**Author:** ![Indistinguishable](https://avatars.discourse-cdn.com/v4/letter/i/90ced4/32.png) [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)\
**Post date:** [June 15, 2011, 10:34am UTC](https://boards.straightdope.com/t/programmers-a-bit-of-code-golf/584245/91 "2011-06-15T10:34:23Z")

</div>

But the one thing you haven’t calculated is an actual path between the nodes… 🙂

---

<div class="post-metadata">

**Author:** ![Indistinguishable](https://avatars.discourse-cdn.com/v4/letter/i/90ced4/32.png) [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)\
**Post date:** [June 15, 2011, 10:41am UTC](https://boards.straightdope.com/t/programmers-a-bit-of-code-golf/584245/92 "2011-06-15T10:41:02Z")

</div>

Also, note, as you presumably realize, that you calculate a lot more than just the information about the minimum weight paths. What you calculate is, for, each weight, the number of paths of edge-number between 0 and n, exclusive, of that weight.

But I insist what you ought to calculate is M = 1 + A + A^2 + A^3 + …, with starting term A^0 and continuing ad infinitum. (Equivalently, in some sense worth thinking more about, M = (1 - A)^{-1}). Then you get the same thing with no edge-number restrictions on the path.

---

<div class="post-metadata">

**Author:** ![septimus](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/septimus/32/410_2.png) [@septimus](https://boards.straightdope.com/u/septimus)\
**Post date:** [June 15, 2011, 12:11pm UTC](https://boards.straightdope.com/t/programmers-a-bit-of-code-golf/584245/93 "2011-06-15T12:11:39Z")

</div>

Returning to the change-making problem for a moment, changing “int” to “long long” (and fixing one typo), the code I posted gets Lance’s answer of 8437020668201 ways to make change of a dollar. (With the “memo” its run is essentially instantaneous; without “memo” my laptop spends two minutes just solving for $0.71.)

But even “long long” isn’t enough to make change for a paltry $1.50. (Even the stingiest Doper will say “just keep the change” before the waitress finishes enumerating those options.)

So, just to prove “we don’t need no steenking bignum packages,” here’s a self-contained program to show that the number of ways to change $75.22 is less than googol^10.

```auto

char Nways[9000][1200];

void addin(char *d, char *s)
{
     int sc, dc, carry = 0;

     while ((sc = *s++) || *d) {
          dc = (*d ? *d : *d + '0') + (sc ? sc - '0' : sc) + carry;
          carry = dc > '9' ? (dc -= 10, 1) : 0;
          *d++ = dc;
     }
     if (carry) *d = '1';
}

main()
{
     int i, j;

     Nways[0][0] = '1';
     for (j = 1; j < 9000; j++) {
          Nways[j][0] = '0';
          if (j >= 1) addin(Nways[j], Nways[j-1]);
          if (j >= 5) addin(Nways[j], Nways[j-5]);
          if (j >= 10) addin(Nways[j], Nways[j-10]);
          printf("There are ");
          for (i = strlen(Nways[j]) - 1; i >= 0; i--)
               printf("%c", Nways[j]*);
          printf(" ways to make change of $%d.%02d
", j/100, j%100);
     }
}

```

---

<div class="post-metadata">

**Author:** ![panamajack](https://avatars.discourse-cdn.com/v4/letter/p/47e85d/32.png) [@panamajack](https://boards.straightdope.com/u/panamajack)\
**Post date:** [June 15, 2011, 5:28pm UTC](https://boards.straightdope.com/t/programmers-a-bit-of-code-golf/584245/94 "2011-06-15T17:28:46Z")

</div>

> [@Indistinguishable](#):
>
> I’m having difficulty understanding the method you are describing here.

Sorry for not responding earlier; I think I must have misremembered how to do this algorithm and can’t quite get it right now. I think all that’s required is just an axis that cuts the polygon (for a quadrilateral, any two alternate points). So you’d need to rotate it. Possibly there’s a way to incorporate the rotation with the sign test, but I’m not sure about that.

---

<div class="post-metadata">

**Author:** ![Chronos](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/chronos/32/134_2.png) [@Chronos](https://boards.straightdope.com/u/Chronos)\
**Post date:** [June 15, 2011, 9:32pm UTC](https://boards.straightdope.com/t/programmers-a-bit-of-code-golf/584245/95 "2011-06-15T21:32:52Z")

</div>

Ah, I think I see what you’re getting at. You rotate your polygon so the axis is horizontal, and then if it’s convex, the vertical component of each point must cross zero only at the two vertices that define the axis. The catch is that you have to try every pair of points as a possible axis. And I think it depends on already having an ordering of the points, too. With only four points, it’d be doable to go through exhaustively, but much more than that, and the method would quickly become unworkable.

---

<div class="post-metadata">

**Author:** ![Indistinguishable](https://avatars.discourse-cdn.com/v4/letter/i/90ced4/32.png) [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)\
**Post date:** [June 16, 2011, 12:48am UTC](https://boards.straightdope.com/t/programmers-a-bit-of-code-golf/584245/96 "2011-06-16T00:48:03Z")

</div>

> [@Indistinguishable](#):
>
> Ok, now for that more surprising second part

Eh, in thinking about it some more, I think this is a better, more straightforward presentation of the calculation (in case anyone is still interested):

Our goal is to calculate the sum of 1/n[sup]2[/sup] over all nonzero integers n. To get a better grip on this sum, we’ll calculate it as f(0), where f(x) is the sum of e[sup]nx[/sup]/n[sup]2[/sup] over all nonzero integers n.

What is the value of introducing this f? Well, we can see quite readily that its second derivative f’‘(x) is the sum of e[sup]nx[/sup] over all nonzero integers n, whose behavior is quite tractable: adding 1 to this and then multiplying by e[sup]x[/sup] - 1 yields 0, so we can conclude that f’‘(x) is constantly -1 (at least, where e[sup]x[/sup] - 1 is invertible). [If you are attentive to such things, you may feel that I am handwaving in the following right over the issue of what happens at the singularities; we should perhaps fully establish that f’’ + 1 is the appropriate Dirac comb]. We can now recover f by double-integrating.

Integrating once, we find that f’(x) = the sum of e[sup]nx[/sup]/n over nonzero n = -x + f’(0). To discover the value of f’(0), we take the average value of both sides of the equation as x runs from 0 to 2ln(K), where K is one half revolution. This causes each e[sup]nx[/sup] to spin uniformly through 2n half revolutions (or n complete revolutions), and thus by symmetry to have an average value of zero. Accordingly, the left hand side of our equation for f’(x) will have an average value of zero; the right hand side’s average value is -ln(K) + f’(0), establishing that f’(0) = ln(K), so that f’(x) = -x + ln(K).

Integrating once more, we find that f(x) = sum of e[sup]nx[/sup]/n[sup]2[/sup] over nonzero n = -x[sup]2[/sup]/2 + ln(K)x + f(0). By the same average value trick, the left hand side goes to zero again, while the right hand side has average value -2ln(K)[sup]2[/sup]/3 + ln(K)[sup]2[/sup] + f(0); thus, f(0) = -ln(K)[sup]2[/sup]/3.

Of course, rather famously, albeit essentially by definition, |ln(K)| = π; thus, we can conclude that our magic number = π[sup]2[/sup]/3.

---

<div class="post-metadata">

**Author:** ![Sage\_Rat](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/sage_rat/32/399_2.png) [@Sage\_Rat](https://boards.straightdope.com/u/Sage_Rat)\
**Post date:** [June 16, 2011, 2:06am UTC](https://boards.straightdope.com/t/programmers-a-bit-of-code-golf/584245/97 "2011-06-16T02:06:12Z")

</div>

> [@septimus](#):
>
> But even “long long” isn’t enough to make change for a paltry $1.50. (Even the stingiest Doper will say “just keep the change” before the waitress finishes enumerating those options.)

I created a memoized version of my code. The ulong appears to run out of bits after $1.47. I can, however, iterate **all** results from $0.01 to $1.47 in an instant with the memoizer.

Oddly enough, I discovered that D has a memoize template as part of their standard library, so I wouldn’t have needed to write it myself.

Here’s the updated version (not using the memoize template):

```auto

import std.stdio;

template NickelNDime(uint target) {
	static ulong[target + 1] memo;
	
	void init() {
		for (int i = 0; i < (target + 1); i++) memo* = ulong.max;
	}
	
	void result(ref ulong total, uint currentValue = 0) {		
		if (memo[currentValue] != ulong.max) {
			total += memo[currentValue];
			return;
		}
		
		ulong before = total;
		uint testValue = currentValue + 1;
		if (testValue == target) ++total;
		else if (testValue < target) {
			result!(target)(total, testValue);
		
			testValue = currentValue + 5;
			if (testValue == target) ++total;
			else if (testValue < target) {
				result!(target)(total, testValue);
			
				testValue = currentValue + 10;
				if (testValue == target) ++total;
				else if (testValue < target) result!(target)(total, testValue);
			}
		}
		memo[currentValue] = total - before;
	}
}

void xtimes(int N : 1)(ref ulong total) {
	NickelNDime!(N).init();
	NickelNDime!(N).result(total);
	writefln("Result: %s -> %s", N, total);
}

void xtimes(int N)(ref ulong total) {
	NickelNDime!(N).init();
	NickelNDime!(N).result(total);
	writefln("Result: %s -> %s", N, total);
	
	total = 0;
	xtimes!(N - 1)(total);
}

int main(string[] args) {
	ulong total = 0;
	xtimes!(147)(total);
	
	return 0;
}

```

The output:

Result: 147 -\> 14808717293036192482  
Result: 146 -\> 10905846801866117440  
Result: 145 -\> 8031586538673604586  
Result: 144 -\> 5914843982327456720  
Result: 143 -\> 4355973650637328062  
Result: 142 -\> 3207947073792568901  
Result: 141 -\> 2362485463324282656  
Result: 140 -\> 1739847147110172123  
Result: 139 -\> 1281306548675186892  
Result: 138 -\> 943615348282072821  
Result: 137 -\> 694923417377506141  
Result: 136 -\> 511774799868230198  
Result: 135 -\> 376895409235975743  
Result: 134 -\> 277563783014941766  
Result: 133 -\> 204411228562686340  
Result: 132 -\> 150538193090780104  
Result: 131 -\> 110863516345880335  
Result: 130 -\> 81645189199009488  
Result: 129 -\> 60127417378172305  
Result: 128 -\> 44280702341880340  
Result: 127 -\> 32610424418495839  
Result: 126 -\> 24015874286374120  
Result: 125 -\> 17686437022024489  
Result: 124 -\> 13025137074083121  
Result: 123 -\> 9592333130025896  
Result: 122 -\> 7064252326403930  
Result: 121 -\> 5202452860496727  
Result: 120 -\> 3831334798812694  
Result: 119 -\> 2821577962208844  
Result: 118 -\> 2077944793358605  
Result: 117 -\> 1530297805717789  
Result: 116 -\> 1126984403852904  
Result: 115 -\> 829965149128674  
Result: 114 -\> 611225981848381  
Result: 113 -\> 450136010263361  
Result: 112 -\> 331501660189414  
Result: 111 -\> 244133657831129  
Result: 110 -\> 179791687475176  
Result: 109 -\> 132407187001858  
Result: 108 -\> 97510977377455  
Result: 107 -\> 71811741675471  
Result: 106 -\> 52885596893101  
Result: 105 -\> 38947479805117  
Result: 104 -\> 28682784583162  
Result: 103 -\> 21123372696492  
Result: 102 -\> 15556260682814  
Result: 101 -\> 11456373462852  
Result: 100 -\> 8437020668201  
Result: 99 -\> 6213425041241  
Result: 98 -\> 4575863005492  
Result: 97 -\> 3369884099556  
Result: 96 -\> 2481743625132  
Result: 95 -\> 1827674553754  
Result: 94 -\> 1345986845429  
Result: 93 -\> 991249008186  
Result: 92 -\> 730003120406  
Result: 91 -\> 537609169519  
Result: 90 -\> 395921073206  
Result: 89 -\> 291575190320  
Result: 88 -\> 214729897750  
Result: 87 -\> 158137354018  
Result: 86 -\> 116459901859  
Result: 85 -\> 85766635119  
Result: 84 -\> 63162646923  
Result: 83 -\> 46515990030  
Result: 82 -\> 34256596869  
Result: 81 -\> 25228194454  
Result: 80 -\> 18579247767  
Result: 79 -\> 13682645647  
Result: 78 -\> 10076553702  
Result: 77 -\> 7420855290  
Result: 76 -\> 5465072286  
Result: 75 -\> 4024740429  
Result: 74 -\> 2964011246  
Result: 73 -\> 2182839459  
Result: 72 -\> 1607547125  
Result: 71 -\> 1183874401  
Result: 70 -\> 871861691  
Result: 69 -\> 642080699  
Result: 68 -\> 472858953  
Result: 67 -\> 348235879  
Result: 66 -\> 256457456  
Result: 65 -\> 188867492  
Result: 64 -\> 139091088  
Result: 63 -\> 102433381  
Result: 62 -\> 75436845  
Result: 61 -\> 55555254  
Result: 60 -\> 40913500  
Result: 59 -\> 30130658  
Result: 58 -\> 22189693  
Result: 57 -\> 16341578  
Result: 56 -\> 12034710  
Result: 55 -\> 8862904  
Result: 54 -\> 6527049  
Result: 53 -\> 4806843  
Result: 52 -\> 3540013  
Result: 51 -\> 2607044  
Result: 50 -\> 1919938  
Result: 49 -\> 1413916  
Result: 48 -\> 1041272  
Result: 47 -\> 766855  
Result: 46 -\> 564762  
Result: 45 -\> 415917  
Result: 44 -\> 306290  
Result: 43 -\> 225558  
Result: 42 -\> 166114  
Result: 41 -\> 122344  
Result: 40 -\> 90105  
Result: 39 -\> 66354  
Result: 38 -\> 48859  
Result: 37 -\> 35979  
Result: 36 -\> 26501  
Result: 35 -\> 19522  
Result: 34 -\> 14378  
Result: 33 -\> 10585  
Result: 32 -\> 7791  
Result: 31 -\> 5738  
Result: 30 -\> 4229  
Result: 29 -\> 3117  
Result: 28 -\> 2295  
Result: 27 -\> 1687  
Result: 26 -\> 1241  
Result: 25 -\> 915  
Result: 24 -\> 676  
Result: 23 -\> 499  
Result: 22 -\> 366  
Result: 21 -\> 268  
Result: 20 -\> 197  
Result: 19 -\> 146  
Result: 18 -\> 109  
Result: 17 -\> 80  
Result: 16 -\> 58  
Result: 15 -\> 42  
Result: 14 -\> 31  
Result: 13 -\> 24  
Result: 12 -\> 18  
Result: 11 -\> 13  
Result: 10 -\> 9  
Result: 9 -\> 6  
Result: 8 -\> 5  
Result: 7 -\> 4  
Result: 6 -\> 3  
Result: 5 -\> 2  
Result: 4 -\> 1  
Result: 3 -\> 1  
Result: 2 -\> 1  
Result: 1 -\> 1

---

<div class="post-metadata">

**Author:** ![Indistinguishable](https://avatars.discourse-cdn.com/v4/letter/i/90ced4/32.png) [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)\
**Post date:** [June 16, 2011, 2:33am UTC](https://boards.straightdope.com/t/programmers-a-bit-of-code-golf/584245/98 "2011-06-16T02:33:58Z")

</div>

Haskell code for the penny-nickel-dime thing:

```auto

numWays = let memo = 1:[sum [numWays (n - x) | x <- [1, 5, 10]] | n <- [1..]]
          in (
 -> case compare n 0 of LT -> 0; EQ -> 1; GT -> memo !! n)

```

For example, numWays 7522 (the number of ways to make $75.22) returns

```auto

996857165439680621133609511643623033006131663020526242857629599571333964243488965310933626339398893662875905261667555279824437190487568377168522706397979278299834335655333463132185462876734351753410484021536570468012018485224661120009452023346833043261397944175737782127416317781564083219517816458800931610401407799753770150554177597496744069401350873353517050277881631981244227123481141676458717680230826966446813037840173691683365918785500656796424863307765169283629054718953289585602850193613710964319115862379488773213968818923246523184026160738017633700828496879978210049455936124670877619621056231605858525742908426356186879515998644529056731007747682836502654178477620261434565030122154571017881247061449546900165438081094564843547330016085780073849857154396638852477987177262313058089593336759890712488165588312874935491907001413083113256276532656876625155717994131920052210232099821027287359287798444061428580796776068011259579582155808321073549093359449477166728628879566251635246987579876

```

, which is 999 digits, as **septimus** pointed out

---

<div class="post-metadata">

**Author:** ![Indistinguishable](https://avatars.discourse-cdn.com/v4/letter/i/90ced4/32.png) [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)\
**Post date:** [June 16, 2011, 2:40am UTC](https://boards.straightdope.com/t/programmers-a-bit-of-code-golf/584245/99 "2011-06-16T02:40:24Z")

</div>

Actually, I double-covered the n = 0 case for no reason. Instead, let me minorly modify that to

```auto

numWays = let memo = 1:[sum [numWays (n - x) | x <- [1, 5, 10]] | n <- [1..]]
          in 
 -> if n < 0 then 0 else memo !! n

```

---

<div class="post-metadata">

**Author:** ![Red\_Skeezix](https://avatars.discourse-cdn.com/v4/letter/r/aca169/32.png) [@Red\_Skeezix](https://boards.straightdope.com/u/Red_Skeezix)\
**Post date:** [June 16, 2011, 3:19am UTC](https://boards.straightdope.com/t/programmers-a-bit-of-code-golf/584245/100 "2011-06-16T03:19:18Z")

</div>

In case anyone was wondering, with the use of bignums and memoization:

in r5rs

```auto

(define numways-usage 
  (lambda (target cur memo)     
      (if (> cur target) 
          0
          (if (= cur target) 
              1
              (if (zero? (vector-ref memo cur)) 
                  (begin
                   (vector-set! memo cur                                 
                                 (+  
                                  (numways-usage target (+ cur 1) memo) 
                                  (numways-usage target (+ cur 5) memo) 
                                   (numways-usage target (+ cur 10) memo)
                                  )                                                                   
                                )
                   (vector-ref memo cur)
                   )
                  (vector-ref memo cur)
                  ) 
              )
          )
      
    )
  )
(define numways (lambda (target) (numways-usage target 0 (make-vector target 0))))
(numways 100000)

```

produces this beaut of a number (13286 digits long):

27883031537599265292098197969818777995298042318083317517189511790785412042170485925186927162947113315931488502750909672417310963706655195712799455644515479690747058263695658120101469022822273768427084667846401940846165819307974859987899364731112614008149042640604622453646289659246092369735585093411072511169643794521819413211255319524157496176171186077799103156753411278237419430044787933498782689102348610043109559630140599855215460132052164296772735535824071163466837678251432054975289175092822839047747084528415485365664964152226339374476701838647439597409023432346260545132689827784017131511295426222831510164947700899966090983380931050118997931519769340872666108598700022611737152347396559106304910366305843550566958311800812118380649196039023930951873312355377457637380925864819444603516670808019112386505529025709105430254443433336523271768639825775765019940314843897528267524004137675424041796269874779579102549071582598650769500754191283607727011586269295650806237214021432427501799848153356626392797950525004285358121445343596352198301640945102816910884712160976307346289738850676756867119770255274684381065381610369798154248213353000897945888794457502383745908774116297219883229444435562241577600261605107486711007636956057362289505254108370354744973568822067968480429678133053941618637001790425236791583971501646199444777455738955983023943749313657870823574840413003176293206481691879596681769290259924636737596720151096261462179103142580811877675712217826613598649098775938189854653904033624390793679707601079123808883968670121731369698177112430173296902470297391395800262762703002803243299293688405171470651966507489186120043305699571780030417254405159774293602928023317716232171079150846596002953573841069707050549147118286341871119061597975789434116908952317261022196615925504360896784666366824127990441786522812109115988500632115846427677911882512146940122440988231923564187599465789529815347439500384693444245297481147483994607972284185201840294783801270147614984935294089378243475263221999344899858358993374624432104406519919141370035551506083314380028290710519622198115919931444805448186707382807925742356826234899596125907592786740133761080011091541928196592440876356946417968814273717531982809982716214121598098737105359399743701281717123243592460153030334024733597589920096742159099396826529442044952984668581171505176876981059284472934361384483432192974696786541311974514510448034484134187341298146113118188806777723758362532231172032731407678575298553856166855338209084258475340613580635030304787548499152065960282484025508015292276422491973048300769651092708750199080316975397152921064329056852492826356409999741166600595574698398468719929942049541799115791667625632334096196905330519078187842894115995717236554250617464848667249586316553043280003118060304804281526401724529312349812269769530796187712019155627362782062370010424707118101679641654005030161325238869185720196791041824785924572727093824846952774051391477007652850017589693117958253690306527247236749320002616001490596179740903096479137308867448678920411927594831143342488843349553874939221669272074535677442996602532063449025407626675164065108217227224077271521591902494761392115634146343384342344148949755822305191620906886148555201964986986409528756842380682626821888612791443805819937190612038947117899299198138442167366542109825664334067731888040248101346411048879774353712459933831993494969456980252152734786598192422588498347259494748883038035702046639081908030950818913028842413258225704893228497810955518712305310804032818970275127087557373151720100996299469730576542200657340209171001559421832204727091629856828242589043496287211168055404056904463930772198490088107650111946372019766586431796398982475517380430040016229832009044469833699993485504620617002180716350645440749424812156392839815842066630404763122821562229840970519092872757852598194369047767891832361196264148537363610329811956587603787899055205285986103136044427224683268201147650520741781108366429264958404525944681403718330748876453698295455609987205479157161005313768153843789184375481978570254709934713377187576968902326270224985008415574620872245803415385417461533716701136374124616623770865095651136863336172651482958158171342669572688082215475067298289328653513010296609566493563318243415919823611211785583648595953264336246232947802104091409975836771844252887374851678073361330189177277421270415080384483583316221325504311429022046417979782521094323732594175934979007021471146635934192019098149063988709378797544252883771645193847574607192987041163315857382722675492573963244504836231410705659065204601035787025088492454897308782544515883917373238817669071193290346014604318396533557105292446402759857323551219097313750679777550628363829436964403907776160389563698957345914109614203205130275802482980338164526014085505802334439945885160411280082286002898252047470186348777744255278932378340924899353001194765239609260506784956366629899157603090719397743545925076247837331210063330740060997541990333906873013025586979861703055841031412310120391816781894309610150186364450959556611237438674119843296287432815590916323187539183953981923590452870244369689410142801259778402499908620473778840366381369902918349282795857054196242116858650843503523427714054836630834747459360334578159201284696388193816764433384086874907608487577243849195428802556058900283114482881250024394469061078910765355357285656595385922276363846914347081719152861381458518262280531072390506321272870318290280708457503990055893373289041284745498758137812374264276362802980430223440358784634510917841325922478384332993982452452666965355013808894418355713681189477447364462848605538154956655333384877514261317022280480797327245986113460915680502355543598621353660003436371557008927947063825483843840701292217522377770348631202389035911541820032438658013431239563589841575383151248349664903530523247837463997496832140145439574914445602486039206177928650918487600014533960066536354495293295939026300942650435788329380016587235981768521815598689583910638043997335639826285317579661483734003423505743017115641027409091322303915442569496444369556108562722778442634957975845611251771470917624389268820989740801781399290704172344738190169985519817323189995920964088865095611376743264388957149553836643347857771569263494427404406565768854733080324480605998346446843060049324389554871969458423977788713201229638419206391489812376679718591212922507285927609993056738088449917092650497383866258904487615227300693077576863473216637079963338359109224133516911248056522994704699272209906957434985282039542114046848842451212115234201571817415372722904820334804545886212204646199264004379656627578713602539191415143467575881229041280021985347823799579914402290572127539426664720043034072759359758243184995735697290607021324129654212511438090556123778993281099691934325269683664556331301496329512742956140040534411578418241997623654025975292880424874625278792493348931458163775922727517210363953249573285522780932922248944725274392592537230998010893087932067981457173639693216792264060917933580191117100317903247497680279331556864076148973530637349384656541389206359252532721325678531448347836868127961404435302789734338288700348207617900864350646563116266819648735172494959193018040976173427580807323769776479713979078927494874702615308691244172851545554008115713514253270967708745570823020609243423289140421018927633712558987461693154619706423224550325382011793431598428244380795625088456863861325337416136757040958096479293115590881999849353534711367299656091603552532535907286994745604400749338533407934077530198240046314875869946487767895722698230300171277265701885463138542930323406889820774794409109652891220992174070557618114600246932874196472652134859995825792435202419247999997110274717853805688221197040091050142525478956377029440411403358739217459847197978224178344422168364050744229833649005920999077397077366889991701002270195780527096244952958943991342829332628624931473768443013254224687840939184695718846176874619876728939156834087671538472643803056884180462807352257190850903719523784903249439146394921183044961368855611775723180887308818786882877527138787565266652334928531866443585354813559898831309017970079782897003489408197715170007469077794826213151021050651149888076939814699036873504585934242172786610434043822677395370247857946479969888444983105125493523518937769933941833379913444634364076420953191349710439622088933989804120576151615160716034318451765541283396850836026385393248374148971229000076924838645581909672881324064006319772208905182990419969924046307216277753494088022903227791800569612391326909603223276530693051433047021548482887591477336572810400191180981871067195114936960955706826804604490482132156986576197308426795086236986564236871634948012128934801331824624699783370454466323163712816225734753722684119628305696016589976660636462946951175098238687142091448633087264431463267424322901965498502120904804980370509888508744010998956249617604576341758478908218273932694166136470310740237080452460629126241570694351236813491087746628150585412854720370952404576833452599724626360764093959236712965933143391123578320052238855120901147074502813187214699121116254549319335202323980455967305051376154448606497785115658201939560519177775881654865385083555350535092573803840241603783659582201039137406689159684638498457808474139159153590716535891397363780133569521977648307596835211895313617385079312506061026698703499484144395586010641462919293202416902072592584313262797991899885290297542946137772036270616777162714766213993267318860459617501854074902178410763984861515057957646562009723725346088087189109931052116068563162092034749684664172398227670616978905259552507509865950583429135265983151894378334196473254739480673610328289831350507436417213921486474300049651050090311281211619948276285412468026564151089989921127285676308082039599752445102206719039046192594452770036729305725597271886259279063859339126462686386149101048184017966556007118969135065138460712120267443696293502938256246521983174674867784049353746819501458074384242319862254149867465412189178813033218202911756849938715318907747109061849890877760464744985286201817254676707314239335058083966680369775931640991014494831908299911993694298143388217745170569393079407770991856397812630205802024375567922877335059306319510758753681207961781583986178863359751967296263391969831338868496201013728597023212361895339601099867926399008679339171094493544847100498538483033615076496169653374422699557544588363598522797898438730604636186840461471715099401406154843221037054977567379066615609666701401643354060946257112947564648467439871341444838281981219207202180921270461688602636063570035121780459549841309290459139403979260934835957241746293152258757404807532742179312122283782552955626040133883640699069848193538295997734931416832146219349782886724129381617963843789417635423076295748384731363850518530976206184371287266019548993669119020970839889184327471936827553999530412978841674837380136738363971222183404645242143096495449202328580494204907805436135887991429802859038185151237976420452572333950445067214365947276881508278305188632518456372093226937922548477750600231481194242812297527589723323738870366755720259691825997907009846507112314715617530890345697689715772808889090522901982967407785839331932749685312573543037615328670160976641898862261153025808544501861198805481463196140925711683486947913431870216347883893217925001274689499485042622041980579455068002830329015892104043122820164718448216061125453332833893895206782927176333498475663487573951226721348120318943471200981477645387409461216180713920862269232039497226015533393159150679626493498287069708343312656119323527193139670208901148935950197310332784416243345463882016526652911938590946300427375941098853425728297298244262588368553364839857084744754100136559537453824085480513776628096418143704236526965201288086669371379501441079007585327377608067752783165955671757863036398903615217807538483132083372272671674590611794908877996926420571046887469778840499519294965858125325276619973229720448107707742323801365495170526725778255131299360446570701044669670906390662472576757820440103064234473036421055675717541946248492665839699927613701110041055067020605578416436087171670850153463248726771468960164035341125837647057218441144169071931949062896583536378495037611063443966041880234402600946582573634304265823945861202920975850765298894955538510208759423024675765469468028725605547557758348160608135345426559557156654817985433448711695044239324721377959217073520338507240749117602213270916667737840733346306278460341461455051588408784685990424210186626804534588109197056413049031781201618470117023993164185186281801094360936199457087047935559102140607084815725037912212587111442938936799391425594474091482566939206422046621738501234746601021449305269278207925945784116482462490566441910650247739616525470172429864090899630106104270881710424736578548003277267888908614133991985632228991719517144808202952085449235504018565509099371586319435262284035002319947697634561706680091493814196191507741934394149899672207253358113852908173240195187423525475454998101288657686011331199910039044401504914394904652504880462150613351053374404228301963416752852653006606755570886383202865905191293163621706521176656341819132661296775567678198643817893480771182717998501469079429038191717265083788284510212893669345

(on preview, I see that Indistinguishable already did it for a big number).

[Previous page](https://boards.straightdope.com/t/programmers-a-bit-of-code-golf/584245.md?page=4)

[Next page](https://boards.straightdope.com/t/programmers-a-bit-of-code-golf/584245.md?page=6)