(onkohan paras keskustelu?)
Löysin joululomien aikaan erään hauskan vanhan ongelman. Tämän on kuulemma esittänyt Edsger Wybe Dijkstra alunperin. Se esiintyy varmasti monessa paikassa ja voi olla useille jo ennestään tuttu. Siinä toivossa, että jollekulle se olisi uusi laitan sen tänne. Linkkaan myöhemmin, loppiaisen jälkeen, mallivastaukseen, jos on tarve.
Tehtävä:
Käytettävissäsi on vain getchar- ja putchar-funktiot tai oman kielesi vastaavat toiminnot. Voit siis lukea yhden merkin kerralla syötteestä ja kirjoittaa yhden merkin kerralla tulostukseen. Saat syötteenä tekstiä, jossa on kirjaimista koostuvia ja välilyönneillä erotettuja sanoja. Syöte loppuu pisteeseen, eli merkkiin .
Ohjelmasi tulee tulostaa syöte niin, että jokainen pariton sana tulostetaan takaperin. Muuten tulostus on syötteen kaltainen. Esimerkki:
syöte: Dijkstra oli aikamoinen äijä.
tulostus: Dijkstra ilo aikamoinen äjiä.
Dijkstran mukaan laskeminen pitää aina aloittaa nollasta, joten yllä on sanat 1 ja 3 käännetty ja sanat 0 ja 2 kääntämättä.
Saat olettaa, että teksti ja sanat ovat järkevää kokoa. Parempi kuitenkin, jos et määrää kovin pieniä ylärajoja niille.
(Huomautus: Muita välimerkkejä ei siis ole. Aakkoset olkoot suomalaiset. Lisäksi saa käyttää valmista ungetc-funktiota tai vastaavaa [joka palauttaa yhden merkin syöttövirtaan], koska sitä vastaavan toiminnon voisi toteuttaa itsekin helposti. Kaikki kikat, kuten sanojen erottamiset split-funktiolla, regexpit ja muut korkeamman tason tekniikat ovat armotta kiellettyjä. Getchar ja putchar käytössä tällä kertaa.)
Postaa koodisi vapaasti alle. Kuvaile ratkaisuasi, jos haluat. Ongelmaa saa sanoa helpoksi, kun sen on ratkaissut mallikkaasti.
~K
Vastaan yhdellä avaimella: Rekursiot.
Edit - saakos käyttää if then else rakennetta?
Jos saa se on aikas helppo.
Mikä on pariton sana?
Jaska kirjoitti:
Mikä on pariton sana?
Joka toinen sana. Alkaen toisesta eli indeksiltään ykkösestä.
#include <stdio.h>
int main() {
int c = getchar(), b[64], n = 0, m = 0;
for (;; c = getchar()) {
if (c != ' ' && c != '.') {
if (n) b[m++] = c;
else putchar(c);
} else {
while (m) putchar(b[--m]);
n = 1 - n;
putchar(c);
if (c == '.') break;
}
}
return 0;
}(onkohan mallikas? :/ ainaki saletisti elite 8)
me irkissä kirjoitti:
15:19 <+sooda> pistänks tahallaan epäselvän version, ilman kommenttei ja yksmerkkisii muuttujanimiä >:)
15:20 < tejeez> joooo!
15:20 < tejeez> sooda: näyttää eliteltä!
Tässä vähemmän elite ratkaisu. Testattu seuraavalla komennolla:
$ gcc -Wall -ansi -pedantic kaanto.c && ./a.out < kaanto.c | less
#include <stdio.h>
#define PUSKURI 512
int main() {
int puskuri[PUSKURI];
int paikka=0;
int tulosta=1; /* 1=tulosta, 0=puskuroi */
/* Lukee silmukassa merkkejä ja kirjoittaa ne puskuriin.
Algoritmi lukee merkin ja kirjoittaa sen puskuriin. Jos
tulosta-lippu on päällä tulostetaan puskurin sisältö siten,
että
1) jos merkkejä on enemmän kuin 1 tulostetaan merkit seuraavasti:
tulosta merkki nro 1
tulosta merkit N-1:stä 2:teen.
tulosta merkki N
2) jos merkkejä on 1, tulosta se.
Huom! Erotinmerkit kuuluvat aina käännettävään merkkijonoon.
*/
while (!feof(stdin)) {
int merkki=getchar();
puskuri[paikka]=merkki;
paikka++;
if (merkki==' ' || merkki=='\n' ||
merkki=='\r' || merkki==EOF) {
tulosta=!tulosta;
}
if (tulosta==1) {
int viimeinen=paikka;
putchar(puskuri[0]);
for (paikka=paikka-1; paikka>1; paikka--)
putchar(puskuri[paikka-1]);
if (viimeinen>1)
putchar(puskuri[viimeinen-1]);
paikka=0;
}
}
return 0;
}Ratkaisu ei kovin kompakti ole, mutta toimii ainakin.
EDIT: Koodissa oli vielä pikku bugikin, korjasin.
kimmo@vyne ~/proj/sanahassu $ gcc -ansi -pedantic -o sanahassu sanahassu.c kimmo@vyne ~/proj/sanahassu $ ./sanahassu Dijkstra oli aikamoinen äijä. Dijkstra ilo aikamoinen äjiä. kimmo@vyne ~/proj/sanahassu $
#include <stdlib.h>
#include <stdio.h>
int main (int argc, char *argv[]) {
int n = 0, vl, sl;
char c, *s;
for (;;) {
if (n == 0) {
while ((c = getchar()) != ' ' && c != '.') {
putchar(c);
}
n = 1;
} else {
s = NULL; vl = 0; sl = 0;
while ((c = getchar()) != ' ' && c != '.') {
++sl;
if (sl > vl) {
vl += 9;
s = realloc(s, vl * sizeof(char));
}
s[sl - 1] = c;
}
while (sl > 0) {
--sl;
putchar(s[sl]);
}
free(s);
n = 0;
}
putchar(c);
if (c == '.') break;
}
putchar('\n');
return 0;
}Peran kirjoitti:
Edit - saakos käyttää if then else rakennetta?
Kaikkea saa käyttää mitä ei erikseen kielletty. Syötteen luku ja kirjoitus on tarkoituksella rajattu, ettei ongelma ratkea jollain paririvisellä skriptillä Perlissä, Pythonissa tai vastaavassa kielessä. (Vaikka ei noita nimenomaisia kieliä ehkä ollut ongelman esitysaikaan vielä.)
Myöhemmin lisää kommentteja. Kiitos ratkaisuista tähän mennessä.
Kaunista koodia täynnä hyviä tapoja:
int main(){int bee=0,see=0;char aa=0,dee[100];while(aa!='.'){aa=getchar();
if(!(bee&1))putchar(aa);if(aa==32||aa=='.'){
if(bee++&1){while(see)putchar(dee[see--]);putchar(aa);}}else if(bee&1)dee[++see]=aa;}return 0;}Hmm, mä muuten tossa vähä niinku alotan laskemisen ykkösestä - en siis tottele dijkstraa! Taulukon eka alkio (0) jää käyttämättömäks. Se oli vaan helpompi tehdä noin :|
Onkohan listatyyppi liian korkean tason tekniikkaa? No, pastean silti:
import sys
stack = []
odd = 0
c = ''
while c != '.':
c = sys.stdin.read(1)
if c in ' .':
while stack:
sys.stdout.write(stack.pop(odd))
sys.stdout.write(c)
odd = -1 - odd
else:
stack.append(c)F:\omat\py\temp>mirror_odds.py Dijkstra oli aikamoinen äijä. Dijkstra ilo aikamoinen äjiä. F:\omat\py\temp>
#include <stdlib.h>
#include <stdio.h>
char s[32], *t=s-1, *r=t, *x=s, c;
void a(), b(), p();
int main(int argc, char *argv[]) {
a();
return 0;
}
void a(){
if (r-s+1) *(t=++r)=' ';
for(;;){
c = getchar();
if (c == ' ') b();
if (c == '.') p();
*(++r) = c;
}
}
void b() {
*(++(t=++r)-1)=' ';
for (;;){
c=getchar();
if (c == ' ') a();
if (c == '.') p();
for (char *q=++r; q>t;) *(--q+1)=*q;
*t = c;
}
}
void p() {
*(++r)='.';
while(x-r-1) putchar( *(x++) );
exit(1);
}Saa yrittää tulkita. :)
Tässä on Forth-kielinen ohjelma tehtävän ratkaisuun:
: oikein key dup dup emit 32 = if drop else 46 =
if 46 else recurse then else then ;
: vaarin key dup dup 32 = if drop else 46 = if
else recurse then then ;
: vtulos dup if emit recurse else drop then ;
: kaanto 0 oikein 46 - if 0 vaarin 46 - if vtulos
32 emit recurse else vtulos 46 emit then
else drop then ;Sana oikein lukee yhden sanan ja näyttää sen oikeinpäin. Sana vaarin lukee yhden sanan pinoon, ja vtulos näyttää sen väärinpäin. Sana kaanto kutsuu vuorotellen näitä sanoja, kunnes lause päättyy pisteeseen.
Nop, laitetaan nyt tämä omakin räpellykseni.
#include <stdio.h>
char k;
char oikein(int c) {
char d;
d=getchar();
if((d=='.')||(d==' ')) {k=d;return d;}
else {
if(c) {putchar(d);oikein(c);}
else {oikein(c);putchar(d);}
}
}
int main() {
int b=1==0;
oikein(1==1);putchar(k);
while(k!='.') {
oikein(b);
putchar(k);b=!b;
}
}- Edit onko tämä kauniimpi?
#include <stdio.h>
char oikein(int c) {
char d;
char nn;
d=getchar();
if((d=='.')||(d==' ')) {return d;}
else {
if(c) {putchar(d);return oikein(c);}
else {nn=oikein(c);putchar(d);return nn;}
}
}
int main() {
int b=1==1;
while(oikein(b)!='.') {
putchar(' ');b=!b;
}
putchar('.');
}Hyvin pitkälti samanlainen kuin peran ratkaisu
#include <stdio.h>
static char c;
void even() {c=getchar();putchar(c); if(c!=' '&&c!='.')even();}
void odd() {char o=c=getchar(); if(c!=' '&&c!='.'){odd();putchar(o);}}
int main() {
while(c != '.') {
even();
if (c != '.') { odd(); putchar(c); }
}
return 0;
}Jos nyt vähän saa nillittää, niin jotkut ovat tulkinneet, että on olemassa nollapituisia sanoja. Vaikkapa foobatin ohjelmalla (tulostus lihavoitu):
(~/temp)(70)% echo "ab ab ab ab." | ./fb [l]ab ab ab ab.[/l] (~/temp)(71)% echo "ab ab ab ab." | ./fb [l]ab ab ba ba.[/l]
En toki voi väittää, että speksini olisi tässä kohdassa yksikäsitteisen selvä. Tuo olisi pitänyt sanoa jo alussa, jotta koetus olisi aivan rehellinen.
Kisahan tämä ei ole, mutta Antti Laaksosen rytmikäs dup dup -esitys voitti kuitenkin. Hurraa Antti!
Nyt lähde:
http://c2.com/cgi/wiki?OddWordProblem
Malliratkaisuja eri kielillä:
http://c2.com/cgi/wiki?OddWordProblemSolutions
Referaatti:
Kyseisessä Wikissä keskusteltiin rinnakkaisrutiineista (coroutines), joista keskustelu jatkui yksinkertaiseen Dijkstran tehtävään, joka todellakin on helppo D:nkin mielestä. Se ei edes vaadi näitä ihmeellisiä rinnakkaisrutiineja.
Siellä viitataan johonkin kiinnostavaan D:n kirjoitukseen, jossa hän kertoo tehtävän käytöstä ohjelmoinnin opettamisessa. Siitä vaan en tiedä valitettavasti enempää. Joskus pitää yrittää löytää linkin takana mainittu kirja. Dee-herralla oli sana ainakin hallussa.
Malliratkaisut tuolla sivulla ovat ehkä kiinnostavampia kuin keskustelu ongelmasta (siellä jo puhutaan työhaastatteluistakin: "liian helppo sellaiseen"). Minusta se ensimmäinen C-kielinen oli erityisen kaunis, vaikka tekniseltä puolelta hieman tehoton (rekursion takia). Monenlaisia esitettiin täälläkin. Tuntuu vähän, että itse D ei olisi kaikkia arvostanut, mutta ehkä tekijät eivät ajatelleetkaan asiaa hänen kannaltaan.
Tehtävässä ei ollut mitään erityistä kompaa tai muuta koukkua. Ajattelin vain tarjota paremman ongelman puutteessa jotain tekemistä niille, joilla on luppoaikaa loppiaisena. Kun noita vastauksia on jo tullut näin monta, niin ehkäpä tuon linkin voi pistää jo tänään. Siirryn sitten valmistelmaan sitä lupaamaani pikku opasta JS:stä ja Mochikitistä.
(En ajatellut, että oma tylsä perusratkaisuni kiinnostaisi ketään. Olen tässä tapellut toisen ohjelmaisen kanssa, jota yritin kirjoittaa nopeasti alta pois. Ei se ollutkaan yhteistyöhaluinen. Tuli sitten pieni koodaajan blokki, mutta murran sen tänään.)
Lopuksi vielä: Ilahduttaa, että tällainen perustehtäväkin sai rutkasti huomiota. Joskus toiste laitan lisää perustehtäviä, ja sillä kertaa paremmin valmisteltuja (eli pitää nuo speksit hioa). Viime syksynähän oli toivetta helpommista putkapostitehtävistä, joten ehkä sellasille on kysyntää. Keskustelun varmaankin asiasta Antin kanssa mailitse ennen.
Tuossa vielä oma, jonka pitäisi laittaa välilyönnit ja pisteet oikein:
#include <stdio.h>
int main()
{
int n = 0, i = 0;
char c = 0, s[128];
while (c != '.')
{
do c = getchar(); while (c == ' ');
if (n != 0 && c != '.') putchar(' ');
if (!(n++ % 2)) for (; (c != ' ' && c != '.'); c = getchar()) putchar(c);
else
{
for (; (c != ' ' && c != '.'); c = getchar()) s[i++] = c;
while (i > 0) putchar(s[--i]);
}
}
putchar('.');
return 0;
}Befunge-98-versio.
004p005p'v00p
v p500,p40!g4<
v <^_,#! #:<
>#@~:' -:#v_$ >'"b5*05g+3pb5*05g+1+:'^\3p'<\2p0"
odd? >e-#v_'@01p^# A dot, print and exit Storage is above here; when hit space or dot,
length >04g#v_,^ < Not space or dot, just print put "^ and a < at end, they lead to the output loop
>b5*05g+3p 05g1+05p^ Not space or dot, store since odd wordHelposti muutettavissa Befunge-93:ksi:
004p005p"v"00p
v p500,p40!g4<
v <^_,#! #:<
>#@~:" "-:#v_$ >75*1-88*05g+3p 88*05g+1+:"^"\3p "<"\2p0"
odd? >e-#v_"@"01p^# A dot, print and exit Storage is above here; when hit space or dot,
length >04g#v_, ^ < Not space or dot, just print put "^ and a < at end, they lead to the output loop
>88*05g+3p 05g1+05p^ Not space or dot, store since odd wordEDIT: Befunge-93-versiosta sen verran, että siinä on vain 14 solua tilaa yhdelle sanalle. Jos tulee pidempi sana vastaan, se kaatunee: riippuu tulkista/kääntäjästä.
Aihe on jo aika vanha, joten et voi enää vastata siihen.