Build a solver for the cow and chicken problem

Question

The cow and chicken problem is a traditional problem for introducing young students to the concept of systems of equations. It goes as follows:

A farmer raises cows and chickens on his farm. His animals have a total of 24 heads and 68 legs. How many cows and how many chickens does he have?

The numbers of heads h and legs l can vary, but the idea of the problem is the same. This problem can't be solved by plugging in a one-variable formula; both variables (the number of cows k, and the number of chickens x) will always be involved in each formula that you can derive directly.

That being said, for this version of the problem, there is a formula k = l/2 - h that you can readily use to obtain the solution of 10 cows and 14 chickens, so it's not too interesting.

Here's a slightly different problem, this time involving cows and chickens who can have a different number of heads and legs.

Your task is to build a program that takes the following inputs (all positive integers):

• h_k, the number of heads a cow has.
• l_k, the number of legs a cow has.
• h_x, the number of heads a chicken has.
• l_x, the number of legs a chicken has.
• h, the total number of heads.
• l, the total number of legs.

: and output k and x, how many cows and chickens the farmer has.

However, depending on the input given, the problem has several states of solvability:

1. There is a solution in the nonnegative integers. The input 1 4 1 2 24 68 (which is the problem above) has the solution 10 14.
2. There is no solution in the nonnegative integers, but there is one in the nonnegative fractional numbers. The input 1 4 1 2 24 67 is an example of this, with a solution of 9.5 14.5.
3. There is no solution in the nonnegative numbers, but one in the integers in general. The input 1 4 1 2 24 36 is an example of this, with a solution of -6 30.
4. There is no solution in either the nonnegative fractional numbers or the integers in general, but one in the real numbers in general. The input 1 4 1 2 24 97 is an example of this, with a solution of 24.5 -0.5.
5. There is no solution at all. The input 2 4 1 2 24 68 is an example of this.
6. There are multiple solutions in the positive integers (and therefore infinitely many solutions in the real numbers). The input 2 4 1 2 24 48 is an example of this. If there is exactly one solution in the positive integers but infinitely many solutions in the real numbers (as is the case with the input 6 9 4 6 10 15 with a solution of 1 1), your solution can treat it as a case of this state.

Your program, given the inputs, must first output which state of solvability the problem has. Only if the problem is in the first state of solvability should you output how many cows and chickens there are, as any other solution is considered an "invalid problem".

The shortest code to do all of the above in any language wins.

• Doorknob: must first output which state of solvability the problem has first This is the hardest part; I've been trying for a while and I still can't even think of a way to start doing it :P
• Howard: @primo No, it's not. Note that 2 4 1 2 means that there are always twice as much legs as heads, no matter how many cows or chicken are involved. Thus there is no way to have 24 heads but 68 legs.
• primo: Sorry, I had my lk and lx switched.
• Peter Taylor: See also this problem over the rationals.

Answer 1

Python 2, 138

a,A,b,B,h,l=input()
d=a*B-b*A
k=B*h-b*l
c=a*l-A*h
if d:K=k/d;C=c/d;z=K>=0<=C;print[[3,[1,K,C]][z],4-2*z][k%d+c%d!=0]
else:print(0==c==k)+5

Expects comma seperated input. The inputs

1, 4, 1, 2, 24, 68
7, 14, 9, 6, 25, 18
1, 4, 1, 2, 24, 67
1, 4, 1, 2, 24, 36
1, 4, 1, 2, 24, 97
2, 4, 1, 2, 24, 68
2, 4, 1, 2, 24, 48

yield the (admittedly not very nicely formatted) answers

[1, 10, 14]
2
2
3
4
5
6

Answer 2

Mathematica (削除) 359 (削除ここまで) 314

About 200 characters went into determining which condition applies.

f@{a_, b_, c_, d_, i_, l_} :=
 Module[{s, t, z = "invalid problem", y = IntegerQ},
 t@n_ := y@n \[And] (n > 0);
 p@n_ := n \[Element] Rationals \[And] n > 0;
 q@n_ := n \[Element] Reals;
 w = Flatten@Quiet@Solve[{d*x + b*k == l, c*x + a*k == i}, {k, x}];
 s = {k, x} /. w;
 Which[w == {}, {5, z},
 Length[w] != 2, {6, z},
 True, If[And @@ (t /@ s), {1, s},
 Which[
 And @@ (p /@ s), {2, z},
 And @@ (y /@ s), {3, z},
 And @@ (q /@ s), {4, z},
 3 == 3, {7, z}]]]]
f[{1, 4, 1, 2, 24, 68}]
f[{7, 14, 9, 6, 25, 18}]
f[{1, 4, 1, 2, 24, 67}]
f[{1, 4, 1, 2, 24, 36}]
f[{1, 4, 1, 2, 24, 97}]
f[{2, 4, 1, 2, 24, 68}]
f[{2, 4, 1, 2, 24, 48}]
f[{1, 4, 1, 2, -23, (3 + I)^2/(5 - I)}]
f[{6, 9, 4, 6, 10, 15}]

{1, {10, 14}}
{2, "invalid problem"}
{2, "invalid problem"}
{3, "invalid problem"}
{4, "invalid problem"}
{5, "invalid problem"}
{6, "invalid problem"}
{7, "invalid problem"}
{6, "invalid problem"}

How it works

The equations d*x+b*k==land c*x+a*k==i express the constraints in the general cow and chickens problem,where

a is "the number of heads per cow"
b is "the number of legs per cow"
c is "the number of heads per chicken"
d is "the number of legs per chicken"
i is "the number of heads"
l is "the number of legs"
k is "the number of cows"
x is "the number of chickens".

Solve returns the real - valued solutions, if any exist, for the cows and chickens, as a list of 2 substitution rules, e.g. {k->10, x-> 14}

If no solutions exist, an empty list is returned.

If the data cannot be processed, Solve will return a different number of elements.

The tests are performed in the following order.

• If there are 0 solutions, condition 5 is satisfied

• If the list of "solution"s has anything other than 2 elements, then condition 6 is satisfied .

• If there are 2 solutions, then

  • if function t yields True, the solution is a pair of non-negative integers, and condition 1 is satisfied.
  • if function p yields True, the solution is a pair of non negative rationals and condition 2 is satisfied.
  • if function q yields True, the solution is a pair of non negative rationals and condition 3 is satisfied.
  • if function y yields True, the solution is a pair of integers and condition 4 is satisfied.
  • Otherwise, condition 7 is satisfied.

Minor Variant of f

g@{a_, b_, c_, d_, i_, l_} := 
 Module[{s, t, z = "invalid problem", y = IntegerQ}, 
 t@n_ := y@n \[And] (n > 0);
 p@n_ := n \[Element] Rationals \[And] n > 0;
 q@n_ := n \[Element] Reals;
 w = Flatten@Quiet@Solve[{d*x + b*k == l, c*x + a*k == i}, {k, x}];
 s = {k, x} /. w;
 Which[w == {}, {5, z, w}, Length[w] != 2, {6, z, w}, True, 
 If[And @@ (t /@ s), {1, s, w}, 
 Which[And @@ (p /@ s), {2, z, w}, And @@ (y /@ s), {3, z, w}, 
 And @@ (q /@ s), {4, z, w}, 3 == 3, {7, z, w}]]]]

g is f` with the additional property that it returns the output of Solve.

g[{1, 4, 1, 2, 24, 68}]
g[{7, 14, 9, 6, 25, 18}]
g[{1, 4, 1, 2, 24, 67}]
g[{1, 4, 1, 2, 24, 36}]
g[{1, 4, 1, 2, 24, 97}]
g[{2, 4, 1, 2, 24, 68}]
g[{2, 4, 1, 2, 24, 48}]
g[{1, 4, 1, 2, -23, (3 + I)^2/(5 - I)}]
g[{6, 9, 4, 6, 10, 15}]

{1, {10, 14}, {k -> 10, x -> 14}}
{2, "invalid problem", {k -> 1/7, x -> 8/3}}
{2, "invalid problem", {k -> 19/2, x -> 29/2}}
{3, "invalid problem", {k -> -6, x -> 30}}
{4, "invalid problem", {k -> 49/2, x -> -(1/2)}}
{5, "invalid problem", {}}
{6, "invalid problem", {x -> 24 - 2 k}}
{7, "invalid problem", {k -> 615/26 + (19 I)/26, x -> -(1213/26) - (19 I)/26}}
{6, "invalid problem", {x -> 5/2 - (3 k)/2}}

Problems falling under condition 6 have multiple solutions, as evidence by the equations. The problem that falls under condition 5 returns an empty set (no solutions).

Note: element and and are single characters in Mathematica.

• Joe Z.: I guess I should have included more test cases. Could you run 7 14 9 6 25 18 by and see if it returns 2?
• DavidC: The additional test case returns 2, as expected.
• DavidC: I also threw in a case with a complex number.
• Joe Z.: It's no longer a positive integer, then. The problem statement says that all inputs will be positive integers.
• DavidC: Exactly. The issue was not whether a complex number is valid for the problem, but rather, what condition should flag it as invalid. It fails each of the first 6 conditions. The 6 conditions, in other words, do not exhaust all of the possible conditions. Hence the need for a seventh "everything else" condition. The condition is satisfied when the first 6 conditions are not met and 3 = 3.

Answer 3

GolfScript, (削除) 105 (削除ここまで) 101 characters

{](=}[phone]base%4/{~*@@*-}%.2=0<{{~)}%}*).{1${1$%0>}%~|2${0<}%~|.++.)p!{{/}+%p}*;;}{;~|!5+p}if

A first (and rather clumsy) approach using GolfScript.

The test cases (see online):

> 1 4 1 2 24 68
1
[10 14]
> 1 4 1 2 24 67
2
> 1 4 1 2 24 36
3
> 1 4 1 2 24 97
4
> 2 4 1 2 24 68
5
> 2 4 1 2 24 48
6

• Joe Z.: Out of curiosity, what does the "1360222640" do?
• Doorknob: @Joe Magic. ​ ​ ​ ​
• Howard: @JoeZ. and Doorknob - what else do you expect from a magic number.
• Howard: @JoeZ. 1360222640 6base 4/ decodes to [[3 4 2 5] [5 0 1 4] [3 0 1 2]] which is used to calculate take product of parameters 3 and 4 and subtract that from product of parameters 2 and 5, ...
• Joe Z.: I was just thinking, it sort of looked like a Unix time stamp, so...

Answer 4

J - 124 characters

(excluding the assignment) Reduced the "invalid problem reporting" clutter (154 -> 124).

chico =: ((>:@],(#"1~-.@*))#.@(0&>,&(>./)(~:<.)) ::({&0 4 5@#))~@(({:%.}:)@; ::(":@(11-#@~.@;@:(%/&.>))))@(((0 2,:1 3);4 5)&({&.>;~))

tests:

t =: ,. 1 4 1 2 24 68;1 4 1 2 24 67;1 4 1 2 24 36 ;1 4 1 2 24 97;2 4 1 2 24 68;2 4 1 2 24 48
chico &.> t
NB. outputs:
+-----------------+
|1 10 14 |
+-----------------+
|2 |
+-----------------+
|3 |
+-----------------+
|4 |
+-----------------+
|5 |
+-----------------+
|6 |
+-----------------+

un-golfed version + comments

NB. Print case and the solution if the state is 0.
print =: (>:@],(#"1~-.@*))
NB. 0 1 2 3 considering binary coding based on positivity and fractionality of
NB. all (>./) elements of the solution. If error caused by a string, then choose 4
NB. or 5 based on length of the string passed.
case =: #.@(0&> ,&(>./) (~:<.)) :: ({&0 4 5@#)
NB. Solve, if error, determine whether multiple solutions exist, then output
NB. '10' else output '9' (just for having length 1 or 2 strings)
solve =: ({:%.}:)@; ::(":@(11-#@~.@;@:(%/&.>)))
NB. Parse input list to obtain matrix and rhs of the system to solve.
format =: (((0 2,:1 3);4 5)&({&.>;~))
NB. Piece the bricks together:
chico_ng =: (print case)~ @ solve @ format
NB. testcases and solutions:
t=: (,.1 4 1 2 24 68;1 4 1 2 24 67;1 4 1 2 24 36;1 4 1 2 24 97;2 4 1 2 24 68;2 4 1 2 24 48)
sols =: ,. 1 10 14 ; (12ドル) ; (13ドル) ;(14ドル) ;(15ドル);(16ドル)
(sols -: chico_ng each t) # 'fail','pass'
+----+
|pass|
+----+

Answer 5

C - (削除) 181 (削除ここまで) 177 characters

a,b,c,d,e,f,g,j;main(){scanf("%d%d%d%d%d%d",&a,&b,&c,&d,&e,&f);g=b*c-a*d;a=b*e-a*f;b=c*f-d*e;j=g?2*(b*g<0||a*g<0)+(b%g&&a%g):b||a?4:5;putchar(j+49);j||printf(" %d %d",b/g,a/g);}

Just a rough sketch, I should be able to get it down to around 150 characters with some massage.