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

<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 13, 2011, 6:03pm UTC](https://boards.straightdope.com/t/programmers-a-bit-of-code-golf/584245/61 "2011-06-13T18:03:34Z")

</div>

My function returns the same truth value regardless of what order the four points are in.

---

<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 13, 2011, 8:16pm UTC](https://boards.straightdope.com/t/programmers-a-bit-of-code-golf/584245/62 "2011-06-13T20:16:05Z")

</div>

> [@Lance\_Turbo](#):
>
> My function returns the same truth value regardless of what order the four points are in.

Yes, this was my intent.

My code was often called “obfuscated” even when I tried otherwise, so I gave up on readability. :smack: Still, I find my C code more readable than Lance’s Mathematica. 😃

```auto

struct xy { double x, y; };

/* can the points p0, p1, p2, p3 form a convex quadrilateral? */
is_cvx_quad(struct xy *p0, struct xy *p1, struct xy *p2, struct xy *p3)
{
#define NR(p,q,r) \
   ((p->x - q->x) * (r->y - p->y) > (r->x - p->x) * (p->y - q->y))
   return 1 ^ NR(p0,p1,p2) ^ NR(p1,p2,p3) ^ NR(p2,p3,p0) ^ NR(p3,p0,p1);
}

```

---

<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 13, 2011, 10:55pm UTC](https://boards.straightdope.com/t/programmers-a-bit-of-code-golf/584245/63 "2011-06-13T22:55:09Z")

</div>

Hmmm…

We’re doing something similar but I am computing the direction of 12 cross products where you seem to be doing only four. Furthermore, I think you get different answers for (0,0), (0,1), (-1,0), (0,-1) versus (0,-1), (-1,0), (0,1), (0,0).

---

<div class="post-metadata">

**Author:** ![MilTan](https://avatars.discourse-cdn.com/v4/letter/m/71e660/32.png) [@MilTan](https://boards.straightdope.com/u/MilTan)\
**Post date:** [June 14, 2011, 2:59am UTC](https://boards.straightdope.com/t/programmers-a-bit-of-code-golf/584245/64 "2011-06-14T02:59:59Z")

</div>

I can’t think of a faster way to do this than **Lance** ’s solution, so my service to the thread is to un-obfuscate his code 🙂

The basic idea is that a quadrilateral is convex as long as each point lies outside the triangle formed by the other three. So the code does exactly that, using a crossproduct-based “in triangle” test. Each test requires three cross products, hence 12 crossproducts.

---

<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 14, 2011, 4:33am UTC](https://boards.straightdope.com/t/programmers-a-bit-of-code-golf/584245/65 "2011-06-14T04:33:50Z")

</div>

If the points were ordered, you do it quickly by just going through the points and checking for sign changes in the difference from one point to the next (e.g. from (1,1)-\>(3,4)-\>(1,7) x is +, then - so 1 sign change; y is + and + so 0 sign changes). A convex polygon will have only two sign changes on a circuit.  
(Completing with (2,3) makes x go +, then -, then +, 3 total changes. With (0,3) you get -, +, +, for only two. In both cases y goes -, -, + giving two total). The nice thing is this works for any polygon.

But I gather that’s not the problem presented. If for some reason multiplication was super expensive you could solve it by finding all the orderings and doing this test, but I think the cross product method is the best for this one.

---

<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, 6:30am UTC](https://boards.straightdope.com/t/programmers-a-bit-of-code-golf/584245/66 "2011-06-14T06:30:23Z")

</div>

> [@panamajack](#):
>
> If the points were ordered, you do it quickly by just going through the points and checking for sign changes in the difference from one point to the next (e.g. from (1,1)-\>(3,4)-\>(1,7) x is +, then - so 1 sign change; y is + and + so 0 sign changes). A convex polygon will have only two sign changes on a circuit.  
> (Completing with (2,3) makes x go +, then -, then +, 3 total changes. With (0,3) you get -, +, +, for only two. In both cases y goes -, -, + giving two total). The nice thing is this works for any polygon.

I’m having difficulty understanding the method you are describing here. Could you describe in detail how it would work for, e.g., (0, 0) -\> (3, 0) -\> (2, 2) -\> (0, 3) [and then back to (0, 0)] vs. (0, 0) -\> (3, 0) -\> (1, 1) -\> (0, 3) [and then back to (0, 0)]? The first of these is convex and the second is non-convex, but the sign change patterns seem the same to me.

---

<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 14, 2011, 7:11am UTC](https://boards.straightdope.com/t/programmers-a-bit-of-code-golf/584245/67 "2011-06-14T07:11:22Z")

</div>

> [@Lance\_Turbo](#):
>
> We’re doing something similar but I am computing the direction of 12 cross products where you seem to be doing only four.

Neat, huh?

One way to think of it is that there are five classes of ordered quadruplets; the count of successes (0, 1, 2, 3, or 4) from the four comparisons determine which of those five classes the ordered quadruplet is in. The even-numbered counts are convex.

The five classes are  
[ul]  
[li] (0) convex quadrilateral, vertexes in counter-clockwise order[/li][li] (1) concave quadrilateral, vertexes in counter-clockwise order[/li][li] (2) convex quadrilateral, vertexes out of order[/li][li] (3) concave quadrilateral, vertexes in clockwise order[/li][li] (4) convex quadrilateral, vertexes in clockwise order[/li][/ul]

Note that the out-of-order case (edges overlapping) occurs only for convex quadrilaterals; a concave quad is always “in order,” or rather the 3 permutations give 3 different concave quadrilaterals.)

> [@Lance\_Turbo](#):
>
> Furthermore, I think you get different answers for (0,0), (0,1), (-1,0), (0,-1) versus (0,-1), (-1,0), (0,1), (0,0).

When my “users” present me with an angle of _exactly_ 180 degrees, and ask me if it’s more or less than 180, they don’t care what answer I give! Maybe your users are pickier! (And, unless Mathematica uses unlimited precision, I’d assume you could provoke a similar problem in your code by substituting x=0.0000000001 or some such for x=0 in your counterexample.)

> [@](#):
>
> I can’t think of a faster way to do this than **Lance** ’s solution,…

Here’s another Doper with **septimus** set to _Ignore this User_. He must be a right-winger. 😃

---

<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 14, 2011, 11:06am UTC](https://boards.straightdope.com/t/programmers-a-bit-of-code-golf/584245/68 "2011-06-14T11:06:05Z")

</div>

Accidentally hit tab-enter. Ignore this post.

---

<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 14, 2011, 11:40am UTC](https://boards.straightdope.com/t/programmers-a-bit-of-code-golf/584245/69 "2011-06-14T11:40:46Z")

</div>

**septimus** , I still think you are ignoring the class of, “not a quadrilateral”, but this is a set of measure zero so depending on circumstances it may not be important.

I’ll propose a new problem. How many ways can I form a line of zero or more pennies, nickels, and dimes so that the total is $1.00? Keep in mind that order matters so nine dimes followed by ten pennies is distinct from ten pennies followed by nine dimes.

There are 915 ways to form such a line so that the total is $0.25.

---

<div class="post-metadata">

**Author:** ![MilTan](https://avatars.discourse-cdn.com/v4/letter/m/71e660/32.png) [@MilTan](https://boards.straightdope.com/u/MilTan)\
**Post date:** [June 14, 2011, 1:49pm UTC](https://boards.straightdope.com/t/programmers-a-bit-of-code-golf/584245/70 "2011-06-14T13:49:00Z")

</div>

**septimus** : Ooh, nice. That’s clever.

**Lance** : Here’s an off-the-top-of-my-head-and-hence-untested simple attempt at your code:

Edit: wait: small bug. Fixing now.

---

<div class="post-metadata">

**Author:** ![MilTan](https://avatars.discourse-cdn.com/v4/letter/m/71e660/32.png) [@MilTan](https://boards.straightdope.com/u/MilTan)\
**Post date:** [June 14, 2011, 1:52pm UTC](https://boards.straightdope.com/t/programmers-a-bit-of-code-golf/584245/71 "2011-06-14T13:52:35Z")

</div>

Here’s the fixed version:

```auto

long total = 0;
for (int dimes = 0; dimes <= 10; dimes++) {
	for (int nickels = 0; nickels <= 20 - 2*dimes; nickels++) {
		int pennies = 100 - 10*dimes - 5*nickels;
		int coins = pennies + nickels + dimes;
		total += fact(coins)/(fact(pennies)*fact(nickels)*fact(dimes));
	}
}

```

---

<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 14, 2011, 1:53pm UTC](https://boards.straightdope.com/t/programmers-a-bit-of-code-golf/584245/72 "2011-06-14T13:53:01Z")

</div>

```auto

int numways(int resid)
{
     return resid < 0 ? 0 :
            resid == 0 ? 1 :
            numways(resid - 1) + numways(resid - 5) + numways(resid - 10);
}

main() { printf("%d
", resid(100)); }

```

---

<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 14, 2011, 2:02pm UTC](https://boards.straightdope.com/t/programmers-a-bit-of-code-golf/584245/73 "2011-06-14T14:02:23Z")

</div>

A version that’s somewhat faster than my previous. 😃  
(Untested; I don’t even know if the answer fits in ‘int.’)

```auto

int numways(int resid)
{
     static int memo[101];
     return resid < 0 ? 0 :
            resid == 0 ? 1 :
            memo[resid] ? memo[resid] :
           (memo[resid] = numways(resid - 1) + numways(resid - 5)
                      + numways(resid - 10));
}

main() { printf("%d
", resid(100)); }

```

---

<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 14, 2011, 2:04pm UTC](https://boards.straightdope.com/t/programmers-a-bit-of-code-golf/584245/74 "2011-06-14T14:04:03Z")

</div>

I think **septimus** gets the correct answer of 8437020668201 while **MilTan** does not, but I’m not 100% sure since neither of you posted your answers.

---

<div class="post-metadata">

**Author:** ![MilTan](https://avatars.discourse-cdn.com/v4/letter/m/71e660/32.png) [@MilTan](https://boards.straightdope.com/u/MilTan)\
**Post date:** [June 14, 2011, 2:07pm UTC](https://boards.straightdope.com/t/programmers-a-bit-of-code-golf/584245/75 "2011-06-14T14:07:59Z")

</div>

No, I don’t get the right answer. I’m trying to figure out why at the moment.

---

<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 14, 2011, 2:18pm UTC](https://boards.straightdope.com/t/programmers-a-bit-of-code-golf/584245/76 "2011-06-14T14:18:52Z")

</div>

I think you’re calculating partitions of 100 into 1’s, 5’s, and 10’s as opposed to compositions. 9 dimes followed by 10 pennies is distinct from 10 pennies followed by 9 dimes.

---

<div class="post-metadata">

**Author:** ![MilTan](https://avatars.discourse-cdn.com/v4/letter/m/71e660/32.png) [@MilTan](https://boards.straightdope.com/u/MilTan)\
**Post date:** [June 14, 2011, 2:21pm UTC](https://boards.straightdope.com/t/programmers-a-bit-of-code-golf/584245/77 "2011-06-14T14:21:59Z")

</div>

> [@Lance\_Turbo](#):
>
> I think you’re calculating partitions of 100 into 1’s, 5’s, and 10’s as opposed to compositions. 9 dimes followed by 10 pennies is distinct from 10 pennies followed by 9 dimes.

Well, the factorial stuff is supposed to take care of that. In that situation, I’m finding the permutations of all 19 coins (= fact(coins)) and dividing out the ones that only differ in the orders of the pennies, or the orders of the dimes. At least, that’s what I’m _supposed_ to be doing.

---

<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 14, 2011, 2:46pm UTC](https://boards.straightdope.com/t/programmers-a-bit-of-code-golf/584245/78 "2011-06-14T14:46:07Z")

</div>

Ok, I see that now. Is it possible that theanswerr is too big to fit in a long? Do you get 915 when you try to calculate the $0.25 case?

---

<div class="post-metadata">

**Author:** ![MilTan](https://avatars.discourse-cdn.com/v4/letter/m/71e660/32.png) [@MilTan](https://boards.straightdope.com/u/MilTan)\
**Post date:** [June 14, 2011, 2:47pm UTC](https://boards.straightdope.com/t/programmers-a-bit-of-code-golf/584245/79 "2011-06-14T14:47:36Z")

</div>

At this point, I think my solution is conceptually correct, but is being foiled by the (obvious in retrospect) overflow caused by factorial. Point goes to **septimus** , for a solution that doesn’t require BigNums 🙂

Edit: **Lance** : Unfortunately, 25! is also too large to fit in a long. I do get the right answer with $0.10, though, for what it’s worth 😉

---

<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 14, 2011, 2:59pm UTC](https://boards.straightdope.com/t/programmers-a-bit-of-code-golf/584245/80 "2011-06-14T14:59:55Z")

</div>

The recursive formula that **septimus** used is the clever answer I was looking for, but I agree that your answer is conceptually correct. I never think about bignums since I work in Mathematica.

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

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