Ohjelmointiharjoitusprobleema :) Sana "PROGRAM" voidaan kirjoittaa kirjaimia sotkien 2520 järjestykseen. Eli kertoma 7! / 2 (7 kirjainta, joista R kaksi kertaa) Tällä sivulla https://petke.info/sanat.html on lista 2519:sta. Mikä listasta puuttuu?
MPRGROA
PetriKeckman kirjoitti:
Eli kertoma 7! / 2 (7 kirjainta, joista R kaksi kertaa)
Itse kirjoittaisin 7! / 2!
Tällä kertaa tulos on tietenkin sama, mutta tästä versiosta näkee suoraan oikean kaavan vaikka R:iä olisi kolme => 7! / 3!
Jos sanassa toistuisi useampia kirjaimia moneen kertaan niin kustakin tulisi erillinen jakaja. Esim. PAPPARA => 7! / 3! / 3! = 140
Yhden puuttuvan tapaus on erityisen helppo ratkaista, koska puuttuva sana muodostuu varmasti jostain toisesta listan sanasta millä tahansa muutoksella. Esimerkiksi alla siirretään sanan ensimmäinen kirjain viimeiseksi ja tarkastetaan, löytyykö tämä sana listasta.
document.body.textContent.match(/[PROGRAM]{7}/g)
.flatMap((s,_,t) => [s.substr(1) + s.substr(0, 1)].filter(p => !t.includes(p)))Jos kuitenkin listasta puuttuu tämän muunnoksen kannalta useampia ”peräkkäisiä” sanoja, tällainen helppo ratkaisu löytää niistä vain yhden (tai ei yhtään, jos kokonainen sanasilmukka puuttuu).
Yleisempään tapaukseen jätän tähän mietittäväksi seuraavan permutaatioiden numerointiin perustuvan ratkaisun (tietenkin mahdollisimman epäselvästi koodattuna).
document.body.textContent.match(/[PROGRAM]{7}/g)
.flatMap(s => [s.replace(/R(?=.*R)/, "r"), s.replace(/R(?!.*R)/, "r")])
.map(s => {
let t0 = s.match(/./g), t = ["P","R","O","G","r","A","M"];
return t0.reduce((sum, c) => {
let i = t.indexOf(c);
t.splice(i, 1);
return sum * (t.length + 1) + i; }, 0);
}
)
.filter((i,_,t) => i && !t.includes(i - 1))
.map(i => i-1)
.map(i => {
let t = ["P","R","O","G","r","A","M"], ii = [];
for (let j = 1; j <= 7; ++j) {
ii[7 - j] = i % j;
i = i / j | 0;
}
return ii.map(i => t.splice(i, 1)[0]).join("")
})
.map(s => s.toUpperCase())
.filter((s,i,t) => t.indexOf(s) == i)Sain tehtävän jotenkuten ratkaistua...REBOL-ohjelmointikielellä. Ootte kyllä taitavia ohjelmoijia, minä en... :(
rebol[] sanat: copy[] ;blockki, taulukko, lista tms. kaikille sana variaatioille lkm: 0 löytyy: func [sanaparametri][ ;löytyykö sana sanat listasta? löydy: false for i 1 (length? sanat) 1 [ if sanat/(i) = sanaparametri [löydy: true] ] return löydy ] until [ sana: random/secure "PROGRAM" ;tuotetaan kaikki sanat äärimmäisen tökeröllä tavalla ;arpomalla 2520 erilaista, heh! en osanut paremmin :( ;Vaikka oikeastaan yllättävän nopeasti sanat näinkin löytyivät! Noin puolessa minuutissa if not (löytyy sana) [ lkm: lkm + 1 print [lkm sana] append sanat sana ] lkm = 2520 ] sanalista: read/lines %sanat.txt ;REBOL:lla ei pystynyt lukemaan netistä sanalistaa, joten tallensin sen koneelle. ;RED-kielellä olisi pystynyt, mutta siinä taas ei toiminut random "PROGRAM" funktio foreach s sanat [ if not (find sanalista s) [ print rejoin ["Listasta puuttui sana " s] ] ] halt
Olipas mulla hölmö aliohjelma, kun se turhaa kävi läpi kaikki sanat, vaikka jos sana löytyi, niin voi suoraa palauttaa true arvon: (pikkasen nopeutu - noin 20 sekuntia tällä tavalla, siis kaikkien variaatiosanojen listan luominen).
löytyy: func [sanaparametri][ ;löytyykö sana sanat listasta? löydy: false for i 1 (length? sanat) 1 [ if sanat/(i) = sanaparametri [return true] ] return löydy ]
Itsellä triviaalin toteutuksen joka kävi kaikki mahdolliset järjestykset (ja vieläpä kahteen kertaan koska R:iä) suoritusaika oli 0,001 s.
//...
var d = new Dictionary<string, bool>();
all(d, "", "PROGRAM");
//...
private static void all(Dictionary<string, bool> d, string start, string rest)
{
if (rest.Length == 1) { d[start + rest] = true; return; }
for (var i=0; i<rest.Length; i++)
{
all(d, start + rest.Substring(i, 1), rest.Substring(0, i) + rest.Substring(i + 1));
}
}(~. 'PROGRAM' A.~ i.!7) -. >;: 1!:1<'sanat.html' MPRGROA
needs net/http
needs dom/html-parse
var data
"PROGRAM" s:len nip a:new ( 0 a:push ) rot times var, result
: get-text \ DOM -- s
a:new swap
(
drop
"text" DOM:attr@ nip
null? if drop else a:push then
) 1 DOM:each drop
" " a:join ;
: fetch-data
"https://petke.info/sanat.html" net:get if
nip >s html:parse get-text data !
else
"Cannot fetch data" throw
then ;
: find-missing \ -- s
result @ data @ ( a:new swap ' a:push s:each! ' n:bxor a:2map= ) s:eachline
"" swap ' s:+ a:each! drop ;
: app:main
fetch-data
find-missing "Puuttuva permutaatio on: %s\n" s:strfmt . ;root@DietPi:~# /opt/8th/bin/rpi64/8th pe.8th Puuttuva permutaatio on: MPRGROA
Aihe on jo aika vanha, joten et voi enää vastata siihen.