6
\$\begingroup\$

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):

  • hk, the number of heads a cow has.
  • lk, the number of legs a cow has.
  • hx, the number of heads a chicken has.
  • lx, 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.

\$\endgroup\$
  • 1
    \$\begingroup\$ 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 \$\endgroup\$ – Doorknob Aug 22 '13 at 14:42
  • \$\begingroup\$ @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. \$\endgroup\$ – Howard Aug 23 '13 at 7:41
  • \$\begingroup\$ Sorry, I had my lk and lx switched. \$\endgroup\$ – primo Aug 23 '13 at 7:42
  • 1
    \$\begingroup\$ See also this problem over the rationals. \$\endgroup\$ – Peter Taylor Aug 27 '13 at 10:16
1
\$\begingroup\$

GolfScript, 105 101 characters

{](=}+1360222640 6base%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
\$\endgroup\$
  • \$\begingroup\$ Out of curiosity, what does the "1360222640" do? \$\endgroup\$ – Joe Z. Aug 23 '13 at 12:53
  • \$\begingroup\$ @Joe Magic. ​ ​ ​ ​ \$\endgroup\$ – Doorknob Aug 23 '13 at 18:36
  • \$\begingroup\$ @JoeZ. and Doorknob - what else do you expect from a magic number. \$\endgroup\$ – Howard Aug 23 '13 at 18:42
  • 1
    \$\begingroup\$ @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, ... \$\endgroup\$ – Howard Aug 23 '13 at 18:46
  • \$\begingroup\$ I was just thinking, it sort of looked like a Unix time stamp, so... \$\endgroup\$ – Joe Z. Aug 27 '13 at 13:27
2
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 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? \$\endgroup\$ – Joe Z. Aug 23 '13 at 1:11
  • \$\begingroup\$ The additional test case returns 2, as expected. \$\endgroup\$ – DavidC Aug 23 '13 at 1:53
  • \$\begingroup\$ I also threw in a case with a complex number. \$\endgroup\$ – DavidC Aug 23 '13 at 2:09
  • \$\begingroup\$ It's no longer a positive integer, then. The problem statement says that all inputs will be positive integers. \$\endgroup\$ – Joe Z. Aug 23 '13 at 2:41
  • \$\begingroup\$ 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. \$\endgroup\$ – DavidC Aug 23 '13 at 10:56
0
\$\begingroup\$

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 ; (1$2) ; (1$3) ;(1$4) ;(1$5);(1$6)
(sols -: chico_ng each t) # 'fail','pass'
+----+
|pass|
+----+
\$\endgroup\$
0
\$\begingroup\$

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.

\$\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.