Kirjautuminen

Haku

Tehtävät

Keskustelu: Yleinen keskustelu: Tehtävä: Mikä sana puuttuu?

Sivun loppuun

PetriKeckman [22.06.2022 06:51:07]

#

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?

Grez [22.06.2022 08:47:01]

#

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

Metabolix [22.06.2022 12:44:34]

#

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)

PetriKeckman [22.06.2022 20:00:42]

#

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

PetriKeckman [22.06.2022 20:14:57]

#

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
]

Grez [23.06.2022 18:07:00]

#

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));
    }
}

jlaire [23.06.2022 20:45:53]

#

    (~. 'PROGRAM' A.~ i.!7) -. >;: 1!:1<'sanat.html'
MPRGROA

jalski [24.06.2022 00:15:19]

#

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

Sivun alkuun

Vastaus

Muista lukea kirjoitusohjeet.
Tietoa sivustosta