topic Re: Gymnast Tower Routine Puzzle in SAS Programming

Gymnast Tower Routine Puzzle

Ksharp — Tue, 13 Dec 2011 07:02:16 GMT

Under influence of FriedEgg , I also want to post a Puzzle. It is from my e-mail.

URL is http://www.gild.com/puzzles/details/320

But I can't understand this Puzzle totally. Is there somebody can explain to me ,it is better to give an example.

December 8 - January 15, 2012(Closes at 11:59pm GMT)

A gymnast center is designing a tower routine consisting of people standing on top of other’s shoulders. For practical and aesthetic reasons, each person must be both shorter and lighter than the person below him or her.

Given the heights and weights of each person in the event, write a program that computes the largest possible number of people in such a tower routine.

Rules and Terms

Why it is the largest number not smallest number?

Ksharp

Re: Gymnast Tower Routine Puzzle

FriedEgg — Tue, 13 Dec 2011 15:30:28 GMT

This reminds me of Pascal's Triangle, somewhat.

You are missing the rest of the puzzle, which requires logging into the website through facebook or linked in:

Puzzle Description

Given the heights and weights of each person in the event, write a program that computes the largest possible number of people in such a tower routine.

The program accepts a single argument on the command line. This argument is a file name, which contains the information you need (the heights and weights of each person). The program must write to the standard output the largest possible number of people in the tower, followed by a single newline (‘\n’).

Input Specifications

The input file consists of a single line.
The line is made of pairs of heights and weights. Each pair is in the format (ht, wt), with ht and wt both positive integers.
Each pair is separated by a whitespace. The line might or might not be terminated by a new line ‘\n’.

There are no gymnasts having the same height or same weight.

Here is an example of a valid input:

(15, 176) (65, 97) (72, 43) (102, 6) (191, 189) (90, 163) (44, 168) (39, 47) (123, 37)

Output Specifications

Your program should output on the standard output the largest possible number of people in the tower, followed by a single newline (‘\n’).

Here is an example of a valid output:

Here is a test case to make sure your program works:

Input

(9430, 3656) (9147, 14355) (133, 14393) (7917, 9513) (3719, 12775) (9902, 3718) (7613, 46) (7339, 6417) (5034, 7800) (11555, 12870) (14959, 9297) (10707, 4664) (3376, 11162) (12748, 1591) (1299, 4653) (9050, 10847) (4412, 1720) (10030, 1402) (1777, 8625) (12725, 1775)

Expected Output

Input

(2850, 1806) (10220, 2971) (5934, 255) (13829, 12522) (9221, 6803) (1643, 8373) (1838, 1330) (5084, 13371) (1874, 2626) (3130, 9037) (4414, 2361) (11327, 1857) (11015, 9180) (10525, 5781) (1172, 10901) (14008, 8653) (5936, 8367) (5407, 6673) (11365, 12291) (6461, 9697) (833, 2632) (13967, 5717) (4363, 7795) (3614, 2924) (7349, 4493) (13674, 2025) (1258, 129) (2478, 14222) (9119, 11612) (2073, 4990)

Expected Output

Gymnast Tower Routine Puzzle

FriedEgg — Tue, 13 Dec 2011 17:23:58 GMT

There is one big issues with the following answer I quickly put together for this problem. ALLPERM has a limit of 18 variables, both of the examples I give above are more than 18, so this will not work for them. However, it does work for the initial question with 9 elements.

filename FT15F001 temp lrecl=512;

data ht_wt;

infile FT15F001 dlm=',)';

input @;

_infile_=prxchange('s/[\(\ ]//o',-1,_infile_);

input (ht wt) (:8.) @@;

parmcards;

(15, 176) (65, 97) (72, 43) (102, 6) (191, 189) (90, 163) (44, 168) (39, 47) (123, 37)

;

run;

proc sql noprint;

select ht, wt into :ht separated by ' ',:wt separated by ' ' from ht_wt;

quit;

data _null_;

array ht[&sqlobs] (&ht);

array wt[&sqlobs] (&wt);

count=0;

do i=1 to fact(&sqlobs);

call allperm(i, of ht

);

call allperm(i, of wt

);

_count=0;

do ii=1 to &sqlobs-1;

if ht[ii]>ht[ii+1] and wt[ii]>wt[ii+1] then _count+1;

end;

count=max(count,_count);

end;

file print;

put count;

run;

Gymnast Tower Routine Puzzle

Linlin — Tue, 13 Dec 2011 18:32:14 GMT

Hi Guys,

I wish I was smart enough to play with you.

Re: Gymnast Tower Routine Puzzle

Ksharp — Wed, 14 Dec 2011 03:08:59 GMT

Haha. I understood what the puzzle means. I can code it correctly now.

Fried Egg , It is not sensible method to use call perm which will waste lots of System Source ,because it might be yield a loop(i.e. you will search the track you have already searched.)

Now I will post my code to GLID to Win My ipad.

Hope I can register at it. But Chinese Government has already forbidden FaceBook , Twitter .... and so on.

I am not sure I can get a right to post.

/*The following is SAS code. it is passed under SAS9.2*/
/*input can change under datalines, output will be generated in SAS log */


data have;
infile datalines dlm='(), ';
input height weight @@;
datalines;
(2850, 1806) (10220, 2971) (5934, 255) (13829, 12522) (9221, 6803) (1643, 8373) (1838, 1330) (5084, 13371) (1874, 2626) (3130, 9037) (4414, 2361) (11327, 1857) (11015, 9180) (10525, 5781) (1172, 10901) (14008, 8653) (5936, 8367) (5407, 6673) (11365, 12291) (6461, 9697) (833, 2632) (13967, 5717) (4363, 7795) (3614, 2924) (7349, 4493) (13674, 2025) (1258, 129) (2478, 14222) (9119, 11612) (2073, 4990)
;
run;



data _null_;
if _n_ eq 1 then do;
if 0 then set have;
declare hash ha(dataset:'have');
declare hiter hi('ha');
 ha.definekey('height','weight');
 ha.definedata('height','weight');
 ha.definedone();

length obs 8 branch _branch $ 20000;
declare hash h(hashexp:20,ordered:'Y');
declare hiter i('h');
 h.definekey('obs');
 h.definedata('branch');
 h.definedone();
end;
set have end=last;  retain max 0;
count+1;obs=1;branch=catx('|',height,weight);h.add();
do while(i.next()=0);  num=(countc(branch,'|')+1)/2;
 max=max(max,num);
_height=input(scan(branch,-2,'|'),best8.);
_weight=input(scan(branch,-1,'|'),best8.);
 do while(hi.next()=0);
  _branch=branch;
  if _height lt height and _weight lt weight then do;
     obs+1;branch=catx('|',branch,height,weight);
     h.add();branch=_branch;end;
 end;
end;
h.clear();
if last then putlog 'The largest possible number is : ' max  ;
run;

Ksharp

Message was edited by: xia keshan ______ A fixed Version.

Gymnast Tower Routine Puzzle

Ksharp — Wed, 14 Dec 2011 03:11:28 GMT

Thank you for your post. Linlin .

I have already send my resume to Mr. Jason.

But I am not sure whether they are interesting with a foreigner.

Gymnast Tower Routine Puzzle

FriedEgg — Wed, 14 Dec 2011 17:13:01 GMT

Nice work Ksharp. As I mentioned in my original post my code was not good. It was a quick, brute-force type, not even fully working since it has a hard limit on number of variables.

Unfortuneatly gild.com and codeeval.com and most other sites I know of similar do not accept SAS language solutions.

Gymnast Tower Routine Puzzle

Ksharp — Thu, 15 Dec 2011 02:31:53 GMT

Hi. FriedEgg.

I found my code above is not efficient. So I recode and optimize it.

As your said . When I intend to post my code to Gild, I can't find a place for SAS, there are many language Java C Rubby Perl, only not include SAS. I can't own my Ipad.

data have;
infile datalines dlm='(), ';
input height weight @@;
datalines;
(2850, 1806) (10220, 2971) (5934, 255) (13829, 12522) (9221, 6803) (1643, 8373) (1838, 1330) (5084, 13371) (1874, 2626) (3130, 9037) (4414, 2361) (11327, 1857) (11015, 9180) (10525, 5781) (1172, 10901) (14008, 8653) (5936, 8367) (5407, 6673) (11365, 12291) (6461, 9697) (833, 2632) (13967, 5717) (4363, 7795) (3614, 2924) (7349, 4493) (13674, 2025) (1258, 129) (2478, 14222) (9119, 11612) (2073, 4990)
;
run;


data _null_;
if _n_ eq 1 then do;
if 0 then set have;
declare hash ha(dataset:'have');
declare hiter hi('ha');
 ha.definekey('height','weight');
 ha.definedata('height','weight');
 ha.definedone();

length obs _height _weight person _person __height __weight 8;
declare hash h(ordered:'Y');
declare hiter i('h');
 h.definekey('obs');
 h.definedata('_height','_weight','_person');
 h.definedone();
end;
set have end=last;  retain max 0;
obs=1; _person=1; _height=height; _weight=weight; h.add();
do while(i.next()=0); 
 max=max(max,_person); person=_person;__height=_height;__weight=_weight;
 do while(hi.next()=0);
  if _height lt height and _weight lt weight then do;
     obs+1;_person+1;_height=height;_weight=weight;
     h.add();_person=person;_height=__height;_weight=__weight;
        end;
 end;
end;
h.clear();
if last then putlog 'The largest possible number is : ' max  ;
run;

Ksharp