Command line challenges

A place to discuss the implementation and style of computer programs.

Moderators: phlip, Moderators General, Prelates

User avatar
Cosmologicon
Posts: 1806
Joined: Sat Nov 25, 2006 9:47 am UTC
Location: Cambridge MA USA
Contact:

Command line challenges

Postby Cosmologicon » Tue Jun 21, 2011 6:09 pm UTC

Describe your challenge and say what tools are allowed. The following commands are generally fair game:

cat echo tr cut yes head tail tee wc sort uniq rev/tac seq/jot expr fold diff join paste grep xargs eval bc sed

If you want to exclude any of these, or add others, that's fine. (I didn't include any file-manipulation commands, so if your challenge involves files, you should add some.) You can say "use anything" if you want, but you might want to specifically disallow outright programming languages like awk, perl, and python. Generally a solution using more primitive tools is preferred, so prefer tr to sed and prefer expr to bc. You can have loops and multiple lines with a semicolon, but prefer one line where possible. Backticks are okay, but avoid them where possible.

#1: List all the years between 2000 and 3000 where July 1st is a Friday. Additional acceptable commands: cal

My solution (uses a for loop):
Spoiler:

Code: Select all

for year in `seq 2000 3000`; do echo $year `cal 7 $year | grep ^31` | grep " " | cut -d" " -f1; done


#2: Determine how many prime numbers there are between 2000 and 3000 such that the sum of their digits is also prime. (No need to list them, just give a count.) Additional acceptable commands: factor

My solution uses expr rather than bc, but it uses sed, which seems like it should be possible to do without. It has 8 pipes.

I'll see if I can think of some more.
Last edited by Cosmologicon on Tue Jun 21, 2011 10:46 pm UTC, edited 1 time in total.

Ended
Posts: 1459
Joined: Fri Apr 20, 2007 3:27 pm UTC
Location: The Tower of Flints. (Also known as: England.)

Re: Command line challenges

Postby Ended » Tue Jun 21, 2011 8:03 pm UTC

Here's my attempt at #2. It doesn't use bc or sed but has a ton of command substitutions.
Spoiler:

Code: Select all

for n in `seq 2000 3000`; do count=$(expr $count + $(expr $(echo $n | factor | wc -w) = 2 \& $(expr $(echo $n | cut -c 1,2,3,4 --output-delimiter=" + ") | factor | wc -w) = 2)); done; echo $count
edit: made it a bit tidier
Generally I try to make myself do things I instinctively avoid, in case they are awesome.
-dubsola

Pepve
Posts: 57
Joined: Wed Jul 28, 2010 9:47 am UTC

Re: Command line challenges

Postby Pepve » Tue Jun 21, 2011 8:18 pm UTC

My solution for #1. It uses date which i think is acceptable (not a fan of strict rules, just a fan of the shell). It's also about 10 times faster than Cosmologicon's. :-P
Spoiler:

Code: Select all

seq 2000 3000 | sed 's/.*/[ `date -d \0-7-1 +%a` = Fri ] \&\& echo \0/' | sh
I like this game.

edit: spelling
Last edited by Pepve on Tue Jun 21, 2011 9:15 pm UTC, edited 2 times in total.

EvanED
Posts: 4331
Joined: Mon Aug 07, 2006 6:28 am UTC
Location: Madison, WI
Contact:

Re: Command line challenges

Postby EvanED » Tue Jun 21, 2011 8:41 pm UTC

Here's my terrible terrible solution to #2. (I was a bit dumb and didn't read the question at first.) This requires zsh's short form of loops.
Spoiler:

Code: Select all

(for i in $(seq 2 2); for j in $(seq 0 9); for k in $(seq 0 9); for l in $(seq 0 9); do isprime=$(echo $(($i+$j+$k+$l)) | factor | egrep "[0-9]+: [0-9]+$" | wc -l); if [ 1 -eq $isprime ]; then echo "$i$j$k$l"; fi; done ) | factor | egrep  "[0-9]+: [0-9]+$" | wc -l


Here's a more explanatory version:
Spoiler:

Code: Select all

(for i in $(seq 2 2);  # Rather than split up a string like 1234, I build it up from each digit.
 for j in $(seq 0 9); # 'i' is just me being dumb and you could get rid of that.
 for k in $(seq 0 9);
 for l in $(seq 0 9); do
     isprime=$(echo $(($i+$j+$k+$l))       # output the sum of the digits (e.g. 1+2+3+4=10)
               | factor                    # output its factors
               | egrep "[0-9]+: [0-9]+$"   # matches a line like "3: 3" but not "4: 2 2"
               | wc -l                     # counts the number of lines: 1=prime, 0=composite
               );
     if [ 1 -eq $isprime ]; then
         echo "$i$j$k$l";            # output the actual number (e.g. 1234) if the digit sum is prime
 fi; done
) # so what comes out of this subshell is a list of numbers whose digits' sums are prime
 | factor                    # factor each of them
 | egrep  "[0-9]+: [0-9]+$"  # select those prime numbers
 | wc -l                     # get a count


Edit: #1 (I did much the same thing as Cosmologicon, though not quite):

Spoiler:

Code: Select all

for i in $(seq 2000 3000); do cal -y 07 $i | egrep -B2 "1 +2$" | head -n1; done | sed "s/     July //"


Annotated (though this is much simpler):
Spoiler:

Code: Select all

for i in $(seq 2000 3000); do
    cal -y 07 $i           # get the calendar for that month
      | egrep -B2 "1 +2$"  # if there's a week with just the 1st and 2nd, select it and output the two previous lines
      | head -n1;          # select the first line, which has the date
done
| sed "s/     July //"     # drop off the "July" prefix, leaving just the year

Ended
Posts: 1459
Joined: Fri Apr 20, 2007 3:27 pm UTC
Location: The Tower of Flints. (Also known as: England.)

Re: Command line challenges

Postby Ended » Tue Jun 21, 2011 9:21 pm UTC

My solution for #1 (somewhat similar to the others using cal):
Spoiler:

Code: Select all

for y in `seq 2000 3000`; do cal 7 $y | x=`grep -E ^\ {13}1` && echo $y; done
Generally I try to make myself do things I instinctively avoid, in case they are awesome.
-dubsola

Pepve
Posts: 57
Joined: Wed Jul 28, 2010 9:47 am UTC

Re: Command line challenges

Postby Pepve » Tue Jun 21, 2011 9:55 pm UTC

I've got two solutions for #2, the prime thing. One with common code factored out (who does that in shell programming?):
Spoiler:

Code: Select all

r="| factor | sed -rn '/^([^:]*): \1/"; sh <<< "seq 2000 3000 ${r}s/(.)(.)(.)(.).*/expr \1 + \2 + \3 + \4/p' | sh ${r}p' | wc -l"

And one that is just very fast (is that even an objective?), and quite readable (i'm sure that's not an ojective):
Spoiler:

Code: Select all

seq 2000 3000 | factor | grep -v '\w\W\w' | (while read i; do echo ${i:0:1}+${i:1:1}+${i:2:1}+${i:3:1}; done) | bc | factor | grep -vc '\w\W\w'

User avatar
Cosmologicon
Posts: 1806
Joined: Sat Nov 25, 2006 9:47 am UTC
Location: Cambridge MA USA
Contact:

Re: Command line challenges

Postby Cosmologicon » Tue Jun 21, 2011 10:45 pm UTC

Wow, great answers!
Pepve wrote:My solution uses date which i think is acceptable (not a fan of strict rules, just a fan of the shell).
Yeah the rules are really more guidelines. Obviously these could be solved much quicker with a python one-liner, but the idea is to encourage using the simpler tools for all they're worth! date is just fine.

#3: This one's a doozy. Without using command substitution, loops, variables, sed, or bc, find the ISBN-10 checksum of each line in a file. That is, you have a file of 9-digit numbers like so:

Code: Select all

999999999
030640615
033025864
061531446
345213637
And your command should output the checksum for each, like so:

Code: Select all

9
2
8
5
X
The checksum is computed as 1 times the first digit, plus 2 times the second digit, etc up to 9 times the 9th digit. This sum is then taken mod 11. Then if the answer is 10, it's replaced with an X.

My solution uses a 19 pipes, 4 cats, 4 cuts, 2 exprs, 3 folds, 2 revs, 3 trs, 2 xargs, a paste, and a diff. (I'm adding diff to the list of approved commands in the OP.) Good luck!

EDIT: Oh yeah, here's my solution for #2. First is my original solution, then there's one that uses Ended's cool trick to get rid of the sed:
Spoiler:

Code: Select all

seq 2000 3000 | factor | grep -v " .* " | sed "s/.* //;s/\(.\)/ + \1/g" | cut -c4- | xargs -L 1 expr | factor | grep -v " .* " | wc -l
seq 2000 3000 | factor | grep -v " .* " | cut -c 1,2,3,4 --output-delimiter=" + " | xargs -L 1 expr | factor | grep -v " .* " | wc -l

EvanED
Posts: 4331
Joined: Mon Aug 07, 2006 6:28 am UTC
Location: Madison, WI
Contact:

Re: Command line challenges

Postby EvanED » Tue Jun 21, 2011 10:56 pm UTC

I want CMS pipelines for that one. Would be pretty easy with that (maybe... there's one thing I'm not sure exactly what to do).

One of these daysyears I'll be able to work on my shell...

maafy6
Posts: 102
Joined: Wed Aug 22, 2007 10:43 pm UTC

Re: Command line challenges

Postby maafy6 » Wed Jun 22, 2011 12:28 am UTC

For #1 - similarish to OP. Relies on the fact that if July 1 is a Friday, so is July 29.

Spoiler:

Code: Select all

for year in {2000..3000}
do
  cal 7 $year | cut -d' ' -f6 | grep 29 &> /dev/null && echo $year
done

User avatar
Cosmologicon
Posts: 1806
Joined: Sat Nov 25, 2006 9:47 am UTC
Location: Cambridge MA USA
Contact:

Re: Command line challenges

Postby Cosmologicon » Mon Jun 27, 2011 2:33 pm UTC

Okay maybe #3 above is a bit too challenging. Here's an easier one:

#4: Convert roman numerals from 1 to 3999 into decimal. So you start with a file like this:

Code: Select all

XLII
CCLXXVIII
CDXLIV
MCMXCIX
MMMDCCCLXXXVIII
And your script needs to output this:

Code: Select all

42
278
444
1999
3888
There are many ways to write roman numerals. I'm using what I believe to be the most standard one. Namely:
  • You never have more than 3 I's, X's, C's, or M's in a row
  • You never have more than one V, L, or D in a row
  • I may appear before V or X, X may appear before L or C, and C may appear before D or M
You only have to properly convert numerals that meet this definition. For instance, if your line fails to convert IIII to 4 or IL to 49, that's fine.

This can be done with a single sed and a single bc. Basically the challenge is to make the string denoted by ??? here as short as possible to make the script work:

Code: Select all

sed '???' numerals.txt | bc
Answers that use other tools besides sed and bc are fine too.

User avatar
phlip
Restorer of Worlds
Posts: 7554
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia
Contact:

Re: Command line challenges

Postby phlip » Tue Jun 28, 2011 8:43 am UTC

Obvious answer:
Spoiler:

Code: Select all

sed 's/I\''([VX]\'')/-1\1/ig;s/X\''([LC]\'')/-10\1/ig;s/C\''([DM]\'')/-100\1/ig;s/I/+1/ig;s/V/+5/ig;s/X/+10/ig;s/L/+50/ig;s/C/+100/ig;s/D/+500/ig;s/M/+1000/ig;s/^/0/'|bc

(Extra quotes in script to stop jsMath from firing - they can be removed to make it a bit shorter). The first 3 substitutions could easily be expanded to accept nonstandard numbers like IL=49:

Code: Select all

sed 's/I\''([VXLCDM]\'')/-1\1/ig;s/V\''([XLCDM]\'')/-5\1/ig;s/X\''([LCDM]\'')/-10\1/ig;s/L\''([CDM]\'')/-50\1/ig;s/C\''([DM]\'')/-100\1/ig;s/D\''([M]\'')/-500\1/ig;s/I/+1/ig;s/V/+5/ig;s/X/+10/ig;s/L/+50/ig;s/C/+100/ig;s/D/+500/ig;s/M/+1000/ig;s/^/0/'|bc

Code: Select all

enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}
[he/him/his]

User avatar
Cosmologicon
Posts: 1806
Joined: Sat Nov 25, 2006 9:47 am UTC
Location: Cambridge MA USA
Contact:

Re: Command line challenges

Postby Cosmologicon » Tue Jun 28, 2011 3:58 pm UTC

Nice. Yours even does lowercase, which was not a requirement. :)

If I remove the ability to do lowercase from your first solution, I count 139 characters in the sed argument. I'm pretty sure I've got one that's 101 characters. I won't post it quite yet, though.

User avatar
eta oin shrdlu
Posts: 450
Joined: Sat Jan 19, 2008 4:25 am UTC

Re: Command line challenges

Postby eta oin shrdlu » Tue Jun 28, 2011 7:54 pm UTC

Cosmologicon wrote:If I remove the ability to do lowercase from your first solution, I count 139 characters in the sed argument. I'm pretty sure I've got one that's 101 characters. I won't post it quite yet, though.
Here's a smaller solution.
Spoiler:

Code: Select all

s/I[VX]\|X[LC]\|C[DM]/-&/g;s/\w/+&*10^\l&/g;y/IVXLCDMivxlcdm/15151510011223/;s/-+/-/g;s/^/0/
Three more characters to parse lowercase too. I'm not very happy about that first regexp; it seems like there should be a more compact way to do that.

User avatar
Cosmologicon
Posts: 1806
Joined: Sat Nov 25, 2006 9:47 am UTC
Location: Cambridge MA USA
Contact:

Re: Command line challenges

Postby Cosmologicon » Tue Jun 28, 2011 8:07 pm UTC

Wow, very clever! 92 characters. Here's my simple 101-character solution, since I don't see any way to improve it by 10 characters:
Spoiler:

Code: Select all

s/M/DD/g;s/CD/+400/;s/D/+500/g;s/C/LL/g;s/XL/+40/;s/L/+50/g;s/X/VV/g;s/IV/+4/;s/V/+5/g;s/I/+1/g;s/.//

User avatar
eta oin shrdlu
Posts: 450
Joined: Sat Jan 19, 2008 4:25 am UTC

Re: Command line challenges

Postby eta oin shrdlu » Thu Jun 30, 2011 5:15 pm UTC

Improved my previous solution to #4. Now at 76 characters:
Spoiler:

Code: Select all

s/I[VX]\|X[LC]\|C[DM]/-&/g;s/\w/&*A^\l&+i/g;y/IVXLCDMivxlcdm/15151510011223/

User avatar
eta oin shrdlu
Posts: 450
Joined: Sat Jan 19, 2008 4:25 am UTC

Re: Command line challenges

Postby eta oin shrdlu » Fri Jul 01, 2011 8:43 pm UTC

Cosmologicon wrote:#3: This one's a doozy. Without using command substitution, loops, variables, sed, or bc, find the ISBN-10 checksum of each line in a file.
With help from the list of commands you used (I don't think I've ever actually used cut or fold before) I came up with this hideous mess:
Spoiler:

Code: Select all

cat isbn.txt | \
  tr '\n' ' ' | fold -w1 | cat -n | cut -c6-8 | grep '[0-9]$' | \
  tr '\t' '*' | xargs -n9 | tr ' ' '+' | fold -w1 | \
  xargs -n35 echo 'substr 0123456789X ( (' | rev | xargs -n39 echo '1 ) 1 + 11 % )' | rev | \
  xargs -n46 expr

User avatar
Cosmologicon
Posts: 1806
Joined: Sat Nov 25, 2006 9:47 am UTC
Location: Cambridge MA USA
Contact:

Re: Command line challenges

Postby Cosmologicon » Wed Jul 06, 2011 6:03 pm UTC

Ah very nice. You used a lot of the same tricks as I did, but I think mine is even more of a horrible mess.
Spoiler:
rev isbn.txt | cat -n | cut -c6,8- | rev | fold -w1 | cat -nE | cut -c6- | fold -w1 | cat -E | paste -sd"* + " | tr "$\t" " " | fold -w120 | cut -b-115 | xargs -L1 expr | xargs -I x expr x % 11 | cat -E | diff -y - - | tr -d "\t" | cut -c3 | tr $ X

User avatar
eta oin shrdlu
Posts: 450
Joined: Sat Jan 19, 2008 4:25 am UTC

Re: Command line challenges

Postby eta oin shrdlu » Wed Jul 06, 2011 7:23 pm UTC

Ooo, lots of nice tricks there. I didn't know you could use "-" for both arguments of diff, which is a pretty cute way of doubling the lines. That's a much nicer way of getting the "X" than my expr substr. (I played around with multiplying the checksum by 101 for a similar effect.) Use of cat -E to get extra characters for later use is pretty too.

Ankit1010
Posts: 135
Joined: Fri Feb 11, 2011 11:32 am UTC

Re: Command line challenges

Postby Ankit1010 » Mon Jul 11, 2011 6:12 am UTC

Well, this is probably too easy compared to the above 4 questions, but here goes:

Make a script to backup all directories inside the current directory into tar files. The tar files can be named whatever you like, but there are additional requirements:
1. After the script has been run 3 times, there should be 3 separate backups of each directory (with different names).
2. If the script is run after this, it replaces the oldest backup with the newest one (so there are always 3 backups at this point),
3. After case 2, it renames the backups appropriately so you know what order they were made in.

Note: I don't have the answer to this. I don't know how to handle the 3 backups in one line. I can do one backup in one line, but to work with 3 backups, and the renaming constraint, I needed to use a full-fledged 19 line shell script.

Trivia: I made this because my brother needed this to backup websites on his server :D

User avatar
phlip
Restorer of Worlds
Posts: 7554
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia
Contact:

Re: Command line challenges

Postby phlip » Mon Jul 11, 2011 6:26 am UTC

Spoiler:
Why rename them?

Code: Select all

mkdir -p backups && cd backups && ls -1r | tail -n +3 | xargs -r rm -r && cd .. && BACKUPDATE="$(date +"%Y%m%d-%H%M%S")" && mkdir -p backups/"$BACKUPDATE" && for i in */; do i="${i:0:${#i}-1}" && [ "$i" != "backups" ] && tar -czf "backups/$BACKUPDATE/$i.tar.gz" "$i"; done


Incidentally, I came up with a few ways to do that final loop... none of them are particularly ideal, though, so I guess it comes down to taste...

Code: Select all

for i in */; do i="${i:0:${#i}-1}" && etc; done

Code: Select all

for i in */; do i="$((dirname "$i/.")) && etc; done

Code: Select all

for i in *; do [ -d "$i" ] && etc; done

Code: Select all

find * -maxdepth 0 -and -type d -and -not -name backups -exec tar -czf "backups/$BACKUPDATE/{}.tar.gz" "{}" \;

Actually, that last one may be the best...

Code: Select all

enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}
[he/him/his]

Ankit1010
Posts: 135
Joined: Fri Feb 11, 2011 11:32 am UTC

Re: Command line challenges

Postby Ankit1010 » Mon Jul 11, 2011 8:55 am UTC

Wait do all of those maintain exactly 3 backups, or are they just for backing up all the directories once?
Your last is similar to the one I came up with just to backup all directories once:

Code: Select all

find . -mindepth 1 -maxdepth 1 -type d | awk 'BEGIN {FS="./"}; {print $2}' | xargs -d '\n' tar czf backup1.tar


Caveats:
1. The above works with the GNU version of xargs, but it won't work on a mac by default, since for some reason they removed the "-d" flag from xargs in their version. You can install the GNU version if you want though.

2. You may have to modify the "print $2" to "print $x" by looking at the format of the output you get from find on your system. For example, "$2" works on my mac, but on linux I think I used $5 or something.

EDIT: I'm still not experienced in shell script, would you mind explaining a few points from the last way you mentioned for the loop?
1.)

Code: Select all

-and -not -name backups
are those arguments to find that tell it not to list the backups dir? or can you use that with any command which outputs?
2.)

Code: Select all

{}.tar.gz" "{}" \;
can you explain what's going on with those {} ? I looked them up before, spent a while trying to figure them out but I never did understand it.

User avatar
phlip
Restorer of Worlds
Posts: 7554
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia
Contact:

Re: Command line challenges

Postby phlip » Tue Jul 12, 2011 12:27 am UTC

Ankit1010 wrote:Wait do all of those maintain exactly 3 backups, or are they just for backing up all the directories once?

All those later bits are just replacements for the for loop at the end of my first command, which I wasn't too happy with. They'd still need to be tacked on to the first part, which does the maintain-3-backups part.

The loop is only necessary because I read the challenge as needing to back up each dir into a separate tarball... if you want to back up everything into a single tarball then it's easier.
Spoiler:

Code: Select all

[the 3-backup-count stuff] && tar -czf backups/$BACKUPDATE.tar.gz */ --exclude=backups
Of course, --exclude is a GNU extension. But then, probably a bunch of stuff in my previous solution was extensions too...


Ankit1010 wrote:1. The above works with the GNU version of xargs, but it won't work on a mac by default, since for some reason they removed the "-d" flag from xargs in their version. You can install the GNU version if you want though.

From what I understand about the GNU tools, it's more likely that they added the -d flag, not that BSD removed it...
[edit] Google confirms - POSIX xargs doesn't have a -d flag.

Ankit1010 wrote:1.)

Code: Select all

-and -not -name backups
are those arguments to find that tell it not to list the backups dir? or can you use that with any command which outputs?

The former.
Ankit1010 wrote:2.)

Code: Select all

{}.tar.gz" "{}" \;
can you explain what's going on with those {} ? I looked them up before, spent a while trying to figure them out but I never did understand it.

They're part of the -exec flag to find - it's where find puts the filename in the executed command.

Code: Select all

enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}
[he/him/his]

User avatar
RoadieRich
The Black Hand
Posts: 1037
Joined: Tue Feb 12, 2008 11:40 am UTC
Location: Behind you

Re: Command line challenges

Postby RoadieRich » Tue Jul 12, 2011 3:25 am UTC

Couldn't you just do something like
Spoiler:
rm backup3.tar; mv backup2.tar backup3.tar; mv backup1.tar backup2.tar; <whatever the backup command is into backup1.tar>
The lack of restriction on names is helpful here, and you've got the metadata to tell you when the backup was made.
73, de KE8BSL loc EN26.

Ankit1010
Posts: 135
Joined: Fri Feb 11, 2011 11:32 am UTC

Re: Command line challenges

Postby Ankit1010 » Tue Jul 12, 2011 10:07 am UTC

RoadieRich wrote:Couldn't you just do something like
Spoiler:
rm backup3.tar; mv backup2.tar backup3.tar; mv backup1.tar backup2.tar; <whatever the backup command is into backup1.tar>
The lack of restriction on names is helpful here, and you've got the metadata to tell you when the backup was made.


That's basically what I did in the full script, except you have to check that backup3.tar, backup2.tar, backup1.tar exist since they may not exist for the first 3 times the script runs.

troyp
Posts: 557
Joined: Thu May 22, 2008 9:20 pm UTC
Location: Lismore, NSW

Re: Command line challenges

Postby troyp » Tue Jul 12, 2011 10:56 am UTC

My belated attempt at #1 in the OP:
Spoiler:

Code: Select all

for y in {2000..3000}; do cal 7 $y|grep ' 2$'>/dev/null && echo $y; done
I spent about quarter of an hour looking up command options writing this, and ironically, ended up not using any.
edit: oops, thats June, not July. fixed it, and shave off a few characters, why not?
edit2: so after deciding to check my code this time by comparing it to other peoples...it turns out that almost all the answers to this are wrong. maafy6's output matches mine (which seems to be right from a few random checks).
Also, Ended's code reminded me of && so I'll get rid of that if statement.
And maafy6's reminded me of {..} so the seq can go too.
edit3: adding spoilers to both my posts from last night (sorry about that)
Last edited by troyp on Tue Jul 12, 2011 10:10 pm UTC, edited 1 time in total.

Ankit1010
Posts: 135
Joined: Fri Feb 11, 2011 11:32 am UTC

Re: Command line challenges

Postby Ankit1010 » Tue Jul 12, 2011 12:44 pm UTC

Well, here's my heavily-plagiarized (from eta oin shrdlu's solution) and illegal (due to using bc and sed) solution for 3:

Code: Select all

cat in | xargs echo | fold -w1 | cat -n | cut -c6-8 | grep '[0-9]$' | tr '\t' '*' | xargs -n9 | tr ' ' '+' | bc | tr '\n' ' ' | sed 's/ / % 11 \'$'\n/g' | bc | sed 's/10/X/g'


Note: \'$'\n needs to be used the to work with the FreeBSD (mac) version of sed. On a GNU sed, its equivalent to just \n.

Props to eta oin shrdlu and Cosmologicon for the "cat -n" trick!

troyp
Posts: 557
Joined: Thu May 22, 2008 9:20 pm UTC
Location: Lismore, NSW

Re: Command line challenges

Postby troyp » Tue Jul 12, 2011 2:00 pm UTC

My rather disappointing solution for #2:
Spoiler:

Code: Select all

for n in {2000..3000}; do echo $n|cut -c 1,2,3,4 --output-delimiter=" + "|xargs expr |xargs expr $n \*|factor|wc -w; done|grep -c '^3$'
This is quite slow. It's ridiculously wasteful, multiplying the number by its digit-sum before factorizing.
This was *supposed* to be a tradeoff for a short, elegant solution, but it didn't turn out that way :-(
I blame the lack of flexibility of the commands involved (xargs doesn't accept final args, expr needs spaces between operators/operands, hardly any possibilities for joining strings take a string rather than character delimiter...it's like they're conspiring against me).
I did manage to avoid sed,awk and bc, though.
edit: spoiler
Last edited by troyp on Tue Jul 12, 2011 10:11 pm UTC, edited 1 time in total.

Fat Pigeon
Posts: 7
Joined: Tue Jul 15, 2008 3:06 am UTC

Re: Command line challenges

Postby Fat Pigeon » Tue Jul 12, 2011 9:35 pm UTC

A solution for #1 relying on the Doomsday Rule instead of the cal function.

Spoiler:

Code: Select all

for y in {2000..2600}; do t=`expr $y + 2 + $y / 4 - $y / 100 + $y / 400`; t=`expr $t % 7`; if [ $t -eq 1 ]; then echo $y `expr $y + 400`; fi; done

User avatar
tetsujin
Posts: 426
Joined: Thu Nov 15, 2007 8:34 pm UTC
Location: Massachusetts
Contact:

Re: Command line challenges

Postby tetsujin » Tue Jul 12, 2011 9:40 pm UTC

Problem 1:
Spoiler:

Code: Select all

# If July 1st is a Friday, then July 2nd is Saturday...  troyp did a similar solution.
# On my system "cal" produces whitespace after the last column, so I need to account for that.
for f in {2000..3000}; do cal 7 $f | grep -qe ' 2 *$' && echo $f; done


Problem 2:
Spoiler:

Code: Select all

for n in {2000..3000}; do (factor $n | grep -q "$n$") && (n2=0;i=0; while ((i<${#n})); do ((n2+=${n:i++:1})); done; factor $n2 | grep -e ': [0-9]*$'); done | wc --lines


The loop over the index variable (i) is only there because I wanted the solution generalized. If we assume the length of the string $n is always four (as it should be, for a four-digit number) the solution can be shortened:

Code: Select all

for n in {2000..3000}; do (factor $n | grep -q "$n$") && factor $((${n:0:1}+${n:1:1}+${n:2:1}+${n:3:1})) | grep -e ': [0-9]*$'; done | wc --lines


Finally, a fully-generalized version that's shorter, using tricks gleaned from the problem 3 solutions:

Code: Select all

for n in {2000..3000}; do (factor $n | grep -q "$n$") && factor $(($(echo $n | fold -w1 | tr '\n' '+')0)) | grep -e ': [0-9]*$'; done | wc --lines


Problem 3:
Frankly, the number of additional restrictions on this one seems pretty silly. I mean, no command substitutions, variables, or loops? I feel like you've removed so much freedom from the solution of the problem that it's in danger of becoming uninteresting. I don't want to type out a solution that's just like all the others, but I don't feel there's much room for me to do anything else, as pretty much everything I know about "fold" and "cut" and so on I'm learning here, now, as we go.
Spoiler:
But, guess what? Rules don't say no process substitution, so, let's try this... :)

Code: Select all

xargs -n1 -Iy bash -c "paste -d '*' <(echo y | fold -w1) <(echo {1..9} | tr ' ' '\n') | (tr '\n' '+'; echo 0)" | xargs -n 1 -I x bash -c 'echo $(((x)%11))' | xargs -n1 -Ix sh -c 'echo x | (grep -v 10 || echo X)'

I didn't know the "fold -w1" trick, so I guess I learned something from other people's solutions. :)

Trimming it down a bit with "here strings":

Code: Select all

# Earlier version had a "head -1" in before the call to "grep" - a relic of a prior attempt, I think.
xargs -n1 -Iy bash -c "paste -d '*' <(<<<y fold -w1) <(echo {1..9} | tr ' ' '\n') | (tr '\n' '+'; echo 0)" | xargs -n 1 -I x bash -c 'echo $(((x)%11)) | (grep -v 10 || echo X)'

Or, without the arbitrary restriction against using "sed":

Code: Select all

xargs -n1 -Iy bash -c "paste -d '*' <(<<<y fold -w1) <(echo {1..9} | tr ' ' '\n') | (tr '\n' '+'; echo 0)" | xargs -n 1 -I x bash -c 'echo $(((x)%11)) | sed -e "s/10/X/;"'


Problem 4 seems to be pretty well covered at this point...
Last edited by tetsujin on Wed Jul 13, 2011 2:02 pm UTC, edited 1 time in total.
---GEC
I want to create a truly new command-line shell for Unix.
Anybody want to place bets on whether I ever get any code written?

troyp
Posts: 557
Joined: Thu May 22, 2008 9:20 pm UTC
Location: Lismore, NSW

Re: Command line challenges

Postby troyp » Tue Jul 12, 2011 10:16 pm UTC

@tetsujin: damn, how did I miss that quiet option for grep? I swear I looked for it. That /dev/null redirection was really annoying me.

Ended
Posts: 1459
Joined: Fri Apr 20, 2007 3:27 pm UTC
Location: The Tower of Flints. (Also known as: England.)

Re: Command line challenges

Postby Ended » Tue Jul 12, 2011 11:11 pm UTC

troyp wrote:edit2: so after deciding to check my code this time by comparing it to other peoples...it turns out that almost all the answers to this are wrong. maafy6's output matches mine (which seems to be right from a few random checks).

Yeah, I noticed this as well. I think it could be due to differing output formats for cal.
Spoiler:
On my system, the last day of the week for cal is Sunday. So for me, your solution finds years where the 1st of July is a Saturday, rather than a Friday.
Generally I try to make myself do things I instinctively avoid, in case they are awesome.
-dubsola

troyp
Posts: 557
Joined: Thu May 22, 2008 9:20 pm UTC
Location: Lismore, NSW

Re: Command line challenges

Postby troyp » Wed Jul 13, 2011 2:10 am UTC

Ah, of course. I should have realized that. Let's see...Cosmologicon's solution gives the same result as mine and maafy6's (somehow thought it was different last night). EvanED's just gives lines with month names on my system, probably due to another cal difference. On my system, cal -y 07 %i is giving the entire year, and ignoring the 07 entirely.
Modifying EvanED's code for my system gives

Code: Select all

for i in $(seq 2000 3000); do cal 7 $i | egrep -B2 "1 +2$" | head -n1; done | sed "s/     July //"
...which agrees with the others.
So I think that's it...they're all working :-)

User avatar
tetsujin
Posts: 426
Joined: Thu Nov 15, 2007 8:34 pm UTC
Location: Massachusetts
Contact:

Re: Command line challenges

Postby tetsujin » Wed Jul 13, 2011 4:13 pm UTC

Ended wrote:Yeah, I noticed this as well. I think it could be due to differing output formats for cal. On my system, the last day of the week for cal is Sunday. So for me, your solution finds years where the 1st of July is a Saturday, rather than a Friday.


I didn't even think of that... Though actually I'd argue that this is a fundamental problem with trying to use simple filters to parse human-readable output to get concrete answers. Using cal for problem 1 is realistically just flat-out the wrong way to go, really. Better to use "date". Shell programming is full of this kind of thing, and it's one of the reasons shell scripts can be so fragile.

"cal" (the version on my system, at least) does have an option to override the locale info, though - so that should be a part of any solution, I guess: "-s" for Sunday as the first day of the week, or "-m" for Monday as the first day.
---GEC
I want to create a truly new command-line shell for Unix.
Anybody want to place bets on whether I ever get any code written?

Ankit1010
Posts: 135
Joined: Fri Feb 11, 2011 11:32 am UTC

Re: Command line challenges

Postby Ankit1010 » Wed Jul 13, 2011 4:38 pm UTC

tetsujin wrote:
Ended wrote:Yeah, I noticed this as well. I think it could be due to differing output formats for cal. On my system, the last day of the week for cal is Sunday. So for me, your solution finds years where the 1st of July is a Saturday, rather than a Friday.


I didn't even think of that... Though actually I'd argue that this is a fundamental problem with trying to use simple filters to parse human-readable output to get concrete answers. Using cal for problem 1 is realistically just flat-out the wrong way to go, really. Better to use "date". Shell programming is full of this kind of thing, and it's one of the reasons shell scripts can be so fragile.

"cal" (the version on my system, at least) does have an option to override the locale info, though - so that should be a part of any solution, I guess: "-s" for Sunday as the first day of the week, or "-m" for Monday as the first day.


Yeah I noticed this too, shell scripts are far too fragile. Do you know of any way of really making sure that they run the same across multiple systems (like maybe bundling your versions of all the tools you use with the script)?

EvanED
Posts: 4331
Joined: Mon Aug 07, 2006 6:28 am UTC
Location: Madison, WI
Contact:

Re: Command line challenges

Postby EvanED » Wed Jul 13, 2011 4:53 pm UTC

Ankit1010 wrote:Yeah I noticed this too, shell scripts are far too fragile. Do you know of any way of really making sure that they run the same across multiple systems (like maybe bundling your versions of all the tools you use with the script)?

Write it in Python. </troll>

User avatar
tetsujin
Posts: 426
Joined: Thu Nov 15, 2007 8:34 pm UTC
Location: Massachusetts
Contact:

Re: Command line challenges

Postby tetsujin » Wed Jul 13, 2011 6:23 pm UTC

EvanED wrote:
Ankit1010 wrote:Yeah I noticed this too, shell scripts are far too fragile. Do you know of any way of really making sure that they run the same across multiple systems (like maybe bundling your versions of all the tools you use with the script)?

Write it in Python. </troll>


The fact that something like that is a viable troll, to me indicates that the situation in the shell needs to be addressed. :)

But to some extent, it's a fundamental problem with the usual approach taken in the shell: The tools and commands that make up the "shell programming language" are quasi-standardized in some cases (posix - but versions actually used usually carry a bunch of non-standard extensions) - but there may be multiple groups writing alternate versions of the command (which would be installed with the same command name), and the output of these programs is usually made for display to a terminal or line printer, for human consumption, which machine-consumption as a secondary goal... Which means the exact format of the output (which we rely upon in scripts) is sensitive even to aesthetic concerns.

Python, Perl, etc. can avoid this situation because there's a namespace system to allow for name clashes, a central authority controlling the development of the core language as well as the module namespace, and processing "human-readable" output normally isn't done. Rather, code written for the language works with the language's data structures, producing very machine-readable answers up until the point when finally data is displayed on-screen.

I don't think anyone really has authority to effectively standardize the environment in which the shell operates - and there's nothing currently in place to provide any kind of namespace support in a reliable fashion (for instance to write a script that says "I want to run GNU find here" and have it work even if GNU find is installed as "gfind" to avoid a clash with another version of "find" that's installed as the standard version) - but one could mitigate the problem of shell script stability somewhat, using the same shells and many of the same tools, if we changed how we work with them: for instance, don't attempt to parse "pretty" program output. Parse something that's more specifically machine-readable instead. In the case of problem 1, using "date" instead of "cal" is a pretty clear-cut solution. (cal's output is meant for human consumption - on the display or on a line printer. So it doesn't matter if there's extra whitespace at the end of the line, or even if the first column is Monday instead of Sunday - a person reading it can adjust. Scripts are going to be a lot more sensitive to such minor changes.) More generally, using programs in such a way that their output is in a format that's consistent and extensible would be the way to go. Just as an example, if the system were populated with tools that took XML input and produced XML output, then you could reliably process the result of commands like "ls -l", even if additional columns are added to the output (for instance, more extensive security information like ACLs, or "fattr" metadata size, file forks if we were dealing with old Mac stuff, etc.). This is because instead of chopping up lines saying "give me the fifth field" or "give me the last field" or "give me characters 5-8 from that line" you'd say "give me the file size field" - and consistently get full precision on the answer (like "15924" bytes as opposed to human-readable quantities like "15k"). Even if you have different versions of a program, possibly even from different sources, they would be able to target a core set of data fields that should be present in their output, while still providing their own extensions on top of that. (Pretty-printing for the user would then be a separate step. Presumably one that would have to be explicitly specified by the user, though of course having that happen automatically would be nice...)

XML is just one possibility, obviously. The important things about such a move are that the output format has to be something extensible, there have to be adequate tools on the system for dealing with data in that format, and preferably there has to be some consensus on what format to use and how to use it. As a bonus, if programs' output format could be somehow explicitly identified, allowing for the possibility of auto-conversion, all the better. It's a little bit hard to visualize any of that actually happening. :)
---GEC
I want to create a truly new command-line shell for Unix.
Anybody want to place bets on whether I ever get any code written?

EvanED
Posts: 4331
Joined: Mon Aug 07, 2006 6:28 am UTC
Location: Madison, WI
Contact:

Re: Command line challenges

Postby EvanED » Wed Jul 13, 2011 6:44 pm UTC

tetsujin wrote:for instance, don't attempt to parse "pretty" program output. Parse something that's more specifically machine-readable instead.

How 'bout this: "for instance, don't parse. pass objects". PowerShell has it right.

Some standard format like XML or, better, JSON would be an okayish alternative, though with a number of drawbacks.

But this should probably move to another thread if we want to continue.

User avatar
tetsujin
Posts: 426
Joined: Thu Nov 15, 2007 8:34 pm UTC
Location: Massachusetts
Contact:

Re: Command line challenges

Postby tetsujin » Wed Jul 13, 2011 7:07 pm UTC

EvanED wrote:
tetsujin wrote:for instance, don't attempt to parse "pretty" program output. Parse something that's more specifically machine-readable instead.

How 'bout this: "for instance, don't parse. pass objects". PowerShell has it right.


That requires an even greater level of coordination to get everything to work together: we'd need a shared runtime environment and a common idea of what objects look like. I was trying to suggest a rather modest course of action, that would work with current shells, only requiring new tools and a change of policy. Sharing objects between processes would be a much more fundamental change.

Though, yeah, PowerShell's pretty cool.

But this should probably move to another thread if we want to continue.


I suppose. Do we want to continue, you think?
---GEC
I want to create a truly new command-line shell for Unix.
Anybody want to place bets on whether I ever get any code written?


Return to “Coding”

Who is online

Users browsing this forum: No registered users and 7 guests