Dominostenen lagen dus zo voor mij.
Nederlandstalige pagina.
De opgaven zijn hier te downloaden.
Voor het geval deze niet langer beschikbaar zijn, kun je ze hier lokaal vinden
Opdrachten A1 tot en met A5 staan hieronder uitgewerkt.
Opdrachten B1 tot en met B4 zijn beschikbaar, tot eind van dit jaar. Maar let op, als je ze download heb je nog maar een week om ze te maken, ze worden namelijk speciaal voor jou gegenereerd. Inmiddels heb ik ze gedownload en gedaan. Alleen snapte ik de "woorden leggen" opgave blijkbaar helemaal niet. Maar goed, ik doe toch buiten mededinging mee.
Opdrachten C1 en C2 zijn knap lastige opdrachten. Daar wagen we een poging aan.
Opgave D is het competitieprogramma van dat jaar, te weten Squares. De Codecup gaat uit van het iets uitgebreidere Box.
Het inkomertje.
Meta [
file: "infolym-2024-2025-a1.meta"
omschrijving: {
Dit programma schrijft naar standaard output de middelste letter of twee letters van het
woord in de invoer. Voor de middelste letter (of letters) en erna telt het woord evenveel letters.
}
]
string: ask/line "Geef een invoerstring: "
;string: to string! read/line
aantal-letters: count string
knip-lengte: 2
if is-odd aantal-letters [
increment aantal-letters
decrement knip-lengte
]
uitvoer: copy cut at string divide aantal-letters 2 knip-lengte
WRITE/LINE uitvoer
BYE
Nog een makkelijke. Twee tijdformaten worden ingevoerd en het verschil moet berekend. We werken de invoer om naar een getal (twee keer) en rekenen het verschil uit. Daarna zetten we het verschil weer om naar een tijdformaat.
Meta [
file: "infolym-2024-2025-a2.meta"
omschrijving: {
Aan het begin en aan het einde van een tijdrit wordt de tijd vastgelegd
in honderdsten van seconden nauwkeurig. Dit programma berekent de
totale tijd tussen vertrektijd en eindtijd in uren, minuten, seconden
en honderdsten van seconden waarbij het aantal minuten en het
aantal seconden nooit groter dan 60 is.
}
]
write {A2 - Tijdrit.
Geef tijdstip 1: }
tijdstip-1: ask/line ""
write {Geef tijdstip 2: }
tijdstip-2: ask/line ""
l-t-1: count tijdstip-1
l-t-2: count tijdstip-2
ums1: copy cut tijdstip-1 (l-t-1 - 3)
ums2: copy cut tijdstip-2 (l-t-2 - 3)
h1: to whole16! copy cut at tijdstip-1 (l-t-1 - 1) 2
h2: to whole16! copy cut at tijdstip-2 (l-t-2 - 1) 2
l-t-1: count ums1
l-t-2: count ums2
s3: 0
s2: 0
s1: 0
while l-t-1 > 2 [
s3: s2
s2: s1
s1: to whole16! copy cut at tijdstip-1 (l-t-1 - 1) 2
ums1: copy cut ums1 (l-t-1 -3)
l-t-1: count ums1
]
write "s1 s2 s3: " write s1 write " " write s2 write " " write s3 write " "
;WRITE/LINE solution
BYE
Deze is makkelijker dan de voorgaande want het moeilijkste daarbij was de omzetting natuurlijk.
Meta [
file: "infolym-2024-2025-a3.meta"
]
invoer: to string! read/line
vorige: ""
while vorige != invoer [
vorige: invoer
nr: 0
for i count invoer [
n: to whole! (copy cut at invoer i 1)
nr: nr + (i * n)
]
invoer: to string! nr
]
write/line invoer
BYE
Bepaal het aantal componenten van een gegeven graaf. Dit kan best wel slim worden gedaan
Meta [
file: "infolym-2024-2025-a4.meta"
omschrijving: {
Bepaal van een graaf uit hoeveel componenten deze bestaat.
Punten N, zijden M. 0 < N ≤ 40 000, 0 < M ≤ 40 000.
}
]
let componenten binary! 40000
change/repeat componenten 1 40000
write {A4 - Graaf.
}
invoer: to string! read/line
de-split: find invoer " "
lengte-invoer: count invoer
lengte-split: count de-split
punten: to natural16! copy cut invoer lengte-invoer - lengte-split
zijden: to natural16! copy cut at invoer (lengte-invoer - lengte-split + 1) lengte-invoer
for index zijden [
invoer: to string! read/line
de-split: find invoer " "
lengte-invoer: count invoer
lengte-split: count de-split
van: to natural16! copy cut invoer lengte-invoer - lengte-split
naar: to natural16! copy cut at invoer (lengte-invoer - lengte-split + 1) lengte-invoer
either van < naar [
kleinste: van
grootste: naar
][
kleinste: naar
grootste: van
]
either 1 = pick componenten grootste [
poke componenten grootste 0
][
if 1 = pick componenten kleinste [
poke componenten kleinste 0
]
]
]
aantal-componenten: to natural16! 0
for index punten [
aantal-componenten: aantal-componenten + pick componenten index
]
write/line aantal-componenten
BYE
Deze opgave draait om het bepalen van de juiste mix
Meta [
file: "infolym-2024-2025-a4.meta"
omschrijving: {
Schudden van 2 * N kaarten, 2 < N < 50
De serie bewerkingen bestaat uit maximaal 60 tekens. Er staan nooit haakjes tussen
haakjes.
}
]
write {A5 - Schudden.
}
let [kaarten kopie] binary! 100
for index 100 [
poke kaarten index index
]
byte! bewaar-kaart
N: to byte! read/line
aantal-kaarten: 2 * N
opdracht: to string! read/line
while not is-empty opdracht [
; Eerste is altijd een cijfer 1 < cijfer < 10 of een letter (b, l, r)
; als het een letter is gelijk verwerken
; als het een cijfer is dan is volgende een letter of een haakje open "("
; als het een letter is, dan cijfer maal de letter uitvoeren
; als het een haakje open is, dan opdracht doorlezen tot haakje sluiten ")"
; en dan de reeks cijfer maal uitvoeren
; subopdracht wordt wat tussen haakjes staat
; Maar binnen de haakjes kan wel cijfer-letter voorkomen
;
teken: copy cut opdracht 1
blr?: find "blr" teken
either blr? [
herhaal: 1
subopdracht: teken
][ ; dus een cijfer
subopdracht: ""
herhaal: to byte! teken
advance opdracht
teken: copy cut opdracht 1
haakje?: find "()" teken
either haakje? [
; lees tot volgende haakje
advance opdracht
teken: copy cut opdracht 1
while not teken = ")" [
either find "23456789" teken [
voeg-nu-toe: to byte! teken
advance opdracht
teken: copy cut opdracht 1
for x voeg-nu-toe [
subopdracht: join/with subopdracht teken
]
][
subopdracht: join/with subopdracht teken
]
advance opdracht
teken: copy cut opdracht 1
]
][
subopdracht: join/with subopdracht teken
]
]
; hier schudden met behulp van subopdracht
write/line subopdracht
for x herhaal [
kopie-subopdracht: subopdracht
while not is-empty kopie-subopdracht [
schud: copy cut kopie-subopdracht 1
either schud = "b" [
bewaar-kaart: pick kaarten 1
for index [1 (aantal-kaarten - 1)] [
poke kaarten index pick kaarten (index + 1)
]
poke kaarten aantal-kaarten bewaar-kaart
][
for i 100 [poke kopie i pick kaarten i]
either schud = "l" [
for i [1 N] [
poke kaarten i * 2 pick kopie i
poke kaarten (i * 2 - 1) pick kopie (i + N)
]
][
for i [1 N] [
poke kaarten (i * 2 - 1) pick kopie i
poke kaarten i * 2 pick kopie (i + N)
]
]
]
advance kopie-subopdracht
]
]
; Tot slot
advance opdracht
]
pak-kaarten: ""
for index [1 aantal-kaarten] [
pak-kaarten: join/with join/with pak-kaarten to string! pick kaarten index " "
]
write/line pak-kaarten
BYE
Hier krijg je een grid van 8 kolommen bij 7 rijen met daarin de getallen van de ogen van dominostenen die erin geplaatst zijn.
Nu moet je uitvissen hoe de stenen gelegen hebben en het aantal stenen die hetzelfde liggen als de steen met 6-6 (inclusief) invullen.
Dit heb ik in eerste instantie logisch opgelost. Toch nog een programmaatje geschreven. In de special Iteratieve Backtracking kun je meer hierover lezen.
Meta [file: domino.meta
omschrijving: {
28 domino stenen
0-0 0-1 1-1 tot en met 6-6
}
]
K= 8
R= 7
; Declareer en initialiseer de grid en andere lijsten
GRID-VELDEN= 56
; Mijn grid
;2 3 3 4 1 1 2 1
;6 5 3 4 1 2 2 4
;0 0 5 5 5 4 1 5
;6 6 4 2 5 6 3 2
;6 0 3 5 2 5 6 0
;2 4 1 3 3 0 1 0
;3 0 4 4 6 6 1 0
let [grid gevuld] binary! GRID-VELDEN
change/repeat gevuld 0 GRID-VELDEN
poke grid 1 2
poke grid 2 3
poke grid 3 3
poke grid 4 4
poke grid 5 1
poke grid 6 1
poke grid 7 2
poke grid 8 1
poke grid 9 6
poke grid 10 5
poke grid 11 3
poke grid 12 4
poke grid 13 1
poke grid 14 2
poke grid 15 2
poke grid 16 4
poke grid 17 0
poke grid 18 0
poke grid 19 5
poke grid 20 5
poke grid 21 5
poke grid 22 4
poke grid 23 1
poke grid 24 5
poke grid 25 6
poke grid 26 6
poke grid 27 4
poke grid 28 2
poke grid 29 5
poke grid 30 6
poke grid 31 3
poke grid 32 2
poke grid 33 6
poke grid 34 0
poke grid 35 3
poke grid 36 5
poke grid 37 2
poke grid 38 5
poke grid 39 6
poke grid 40 0
poke grid 41 2
poke grid 42 4
poke grid 43 1
poke grid 44 3
poke grid 45 3
poke grid 46 0
poke grid 47 1
poke grid 48 0
poke grid 49 3
poke grid 50 0
poke grid 51 4
poke grid 52 4
poke grid 53 6
poke grid 54 6
poke grid 55 1
poke grid 56 0
oplossing?: false
; Array voor gelegde dominostenen
MAX-INDEX-DOMINO= 49
; 49 maakt het makkelijker om de stenen te indexeren
; 0-0: 1 dummies hier
; 0-1: 2 1-1: 9
; 0-2: 3 1-2: 10 2-2: 17
; 0-3: 4 1-3: 11 2-3: 18 3-3: 25
; 0-4: 5 1-4: 12 2-4: 19 3-4: 26 4-4: 33
; 0-5: 6 1-5: 13 2-5: 20 3-5: 27 4-5: 34 5-5: 41
; 0-6: 7 1-6: 14 2-6: 21 3-6: 28 4-6: 35 5-6: 42 6-6: 49
; domino-index: domino-a * 7 + domino-b + 1
; Orientatie wordt gebruikt om aan het einde de stenen
; met gelijke orientatie als de 6-6 te tellen.
let [gelegd orientatie] binary! MAX-INDEX-DOMINO
change/repeat gelegd 0 MAX-INDEX-DOMINO
change/repeat orientatie 0 MAX-INDEX-DOMINO
; Arrays om het bord op te bouwen, tbv backtracking
; veldnummer en richting zijn nodig, we kunnen uit de grid halen welke steen het is.
; maar dan moeten we opnieuw kijken en bepalen welke het is/was
NUMBER-OF-DOMINOS= 28
let [bord richting steen] binary! NUMBER-OF-DOMINOS
change/repeat bord 0 NUMBER-OF-DOMINOS
change/repeat richting 0 NUMBER-OF-DOMINOS
change/repeat steen 0 NUMBER-OF-DOMINOS
; Aanpak: We kijken naar hoe we denken dat de volgende steen ligt:
; vertikaal of horizontaal.
; Als de steen (combinatie) al gebruikt is kan deze niet opnieuw worden gebruikt,
; dus kan de steen niet zo liggen.
; Als we een item van de stack pakken, dan pakken we een plek en een orientatie,
; niet een echte steen. Het grid is namelijk al gevuld.
; Verder als we een vertikale orientatie hebben dan moeten we backtracken.
; Omdat we van boven naar beneden opbouwen kunnen we vanaf die kant niet halve stenen insluiten
; dit kan alleen op de laatste rij, waarbij er geen oneven aantal vakken mag worden ingesloten.
; Ga zo alle lege cellen langs.
; Als we aan het einde komen en alle plekken zijn ingevuld, dan hebben we de oplossing
; Declareer de Stack.
let [stack-plaats stack-richting] binary! 60
change/repeat stack-plaats 0 60
change/repeat stack-richting 0 60
constant byte! [
HORIZONTAAL= 1
VERTIKAAL
]
; Initialisaties zie boven
stackpointer: 0
bordpointer: 0
domino-start: 1
;Vul de stack met initiele opties
increment stackpointer
poke stack-plaats stackpointer domino-start
poke stack-richting stackpointer VERTIKAAL
increment stackpointer
poke stack-plaats stackpointer domino-start
poke stack-richting stackpointer HORIZONTAAL
;
; De basis lus constructie
;
while stackpointer [
; Haal het bovenste item (cel, keuze) van de stack(s)
domino-start: pick stack-plaats stackpointer
ligging: pick stack-richting stackpointer
decrement stackpointer
while domino-start <= pick bord bordpointer [
; We moeten de vorige toevoeging op het bord ongedaan maken.
reset-start: pick bord bordpointer
reset-richting: pick richting bordpointer
reset-steen: pick steen bordpointer
either HORIZONTAAL = reset-richting [
reset-eind: reset-start + 1
][
reset-eind: reset-start + K
]
poke gevuld reset-start 0
poke gevuld reset-eind 0
poke gelegd reset-steen 0
poke orientatie reset-steen 0
poke bord bordpointer 0
poke richting bordpointer 0
poke steen bordpointer 0
decrement bordpointer
]
; schoon alle 'gelegd' stenen waarvan de ligging/plaats groter of gelijk is aan
; de huidige waarde van domino-start
for schoon MAX-INDEX-DOMINO [
if domino-start <= pick gelegd schoon [
poke gelegd schoon 0
poke orientatie schoon 0
]
]
; Voorwaardes
; check mag deze plaatsing wel?
either ligging = HORIZONTAAL [
; mag horizontaal?
if 0 = remainder domino-start 8 [
; Nee
continue
]
][
; mag vertikaal?
vertikaal-leggen?: false
either domino-start <= 40 [
vertikaal-leggen?: true
][
if domino-start <= 48 [
; laatste rij? ingesloten gebied?
ingesloten: 0
t: 49
while t < (domino-start + 8) [
if 0 = pick gevuld t [increment ingesloten]
increment t
]
if is-even ingesloten [vertikaal-leggen?: true]
]
]
if not vertikaal-leggen? [
continue
]
]
; Vind de waardes uit de grid, kijk of de steen misschien al is gelegd?
kant-1: pick grid domino-start
either HORIZONTAAL = ligging [
domino-eind: domino-start + 1
][
domino-eind: domino-start + 8
]
; Mag niet zo liggen als veld al gevuld is, eigenlijk alleen voor horizontaal nuttig
; vanwege de manier van doorlopen van de mogelijkheden.
if any [1 = pick gevuld domino-start
1 = pick gevuld domino-eind ][
continue
]
kant-2: pick grid (domino-eind)
either kant-1 < kant-2 [
kant-a: kant-1
kant-b: kant-2
][
kant-a: kant-2
kant-b: kant-1
]
domino-index: kant-a * 7 + kant-b + 1
if 0 < pick gelegd domino-index [
; Steen is al elders gelegd dus geprobeerd, kan niet op twee plaatsen liggen
continue
]
; Pas de keuze toe op de huidige positie
poke gevuld domino-start 1
poke gevuld domino-eind 1
poke gelegd domino-index domino-start
poke orientatie domino-index ligging
increment bordpointer
poke bord bordpointer domino-start
poke richting bordpointer ligging
poke steen bordpointer domino-index
; Check of we het grid al opgevuld hebben
either NUMBER-OF-DOMINOS = bordpointer [
; Bord is vol, we hebben een geldige oplossing bereikt
oplossing?: true
break
][
; Zo niet dan moeten we verder gaan met het vullen van de stack
; met mogelijkheden, geen drukte nu om of dat wel kan.
; Zoek de eerstvolgende lege plaats
for veld GRID-VELDEN [
if 0 = pick gevuld veld [
eerste-leeg: veld
break
]
]
; Vertikaal
increment stackpointer
poke stack-plaats stackpointer eerste-leeg
poke stack-richting stackpointer VERTIKAAL
; Horizontaal
increment stackpointer
poke stack-plaats stackpointer eerste-leeg
poke stack-richting stackpointer HORIZONTAAL
;
] ; Einde either
;
;
] ; Einde lusconstructie
;
either oplossing? [
tel: 0
als-zes-zes: pick orientatie MAX-INDEX-DOMINO
for d-index MAX-INDEX-DOMINO [
if als-zes-zes = pick orientatie d-index [
increment tel
]
]
write/line tel
][
write/line "Geen oplossing"
]
Ook nog even een stukje code toegevoegd om een svg te tekenen.
Dominostenen lagen dus zo voor mij.
; Maak een svg van het grid, omdat het kan.
; Declare output file
file-out: ./domino.svg
svg-start: {<?xml version="1.0" standalone="no"?>
<svg width="80mm" height="70mm" viewBox="0 0 80 70" xmlns="http://www.w3.org/2000/svg" version="1.1">
<desc>Domino diagram created with Meta by arnoldvanhofwegen.com</desc>
<!-- Grid Lines -->
<g stroke="black" stroke-width="1">
<!-- Vertical lines for 8 columns -->
<line x1="0" y1="0" x2="0" y2="70" />
<line x1="10" y1="0" x2="10" y2="70" />
<line x1="20" y1="0" x2="20" y2="70" />
<line x1="30" y1="0" x2="30" y2="70" />
<line x1="40" y1="0" x2="40" y2="70" />
<line x1="50" y1="0" x2="50" y2="70" />
<line x1="60" y1="0" x2="60" y2="70" />
<line x1="70" y1="0" x2="70" y2="70" />
<line x1="80" y1="0" x2="80" y2="70" />
<!-- Horizontal lines for 7 rows -->
<line x1="0" y1="0" x2="80" y2="0" />
<line x1="0" y1="10" x2="80" y2="10" />
<line x1="0" y1="20" x2="80" y2="20" />
<line x1="0" y1="30" x2="80" y2="30" />
<line x1="0" y1="40" x2="80" y2="40" />
<line x1="0" y1="50" x2="80" y2="50" />
<line x1="0" y1="60" x2="80" y2="60" />
<line x1="0" y1="70" x2="80" y2="70" />
</g>
}
svg-text: { <!-- Text for each cell (0-6) -->
<g font-family="Arial" font-size="6" text-anchor="middle" fill="black">
}
xco: 5
yco: 7
for grid-index GRID-VELDEN [
aantal-ogen: pick grid grid-index
svg-text: join/with join/with join/with join/with join/with join/with join/with svg-text
{<text x="} to string! xco {" y="} to string! yco {">} to string! aantal-ogen {</text>
}
xco: xco + 10
if 0 = remainder grid-index 8 [
xco: 5
yco: yco + 10
]
]
svg-text-sluit: { </g>
}
either als-zes-zes = 1 [
kleur-horizontaal: "lime"
kleur-vertikaal: "OrangeRed"
][
kleur-horizontaal: "OrangeRed"
kleur-vertikaal: "lime"
]
svg-domino-groep: { <!-- Colored frames for two-cell groupings -->
<!-- Horizontal 2-cell frame example at row 1, columns 1-2 -->
}
for d-index MAX-INDEX-DOMINO [
; bepaal plaats
plaats: pick gelegd d-index
if plaats = 0 [continue]
y-index: divide to byte! plaats 8
x-index: remainder plaats 8
if x-index = 0 [x-index: 8 decrement y-index]
yco: y-index * 10 + 0.5
xco: (x-index - 1) * 10 + 0.5
; bepaal orientatie en kleur
either 1 = pick orientatie d-index [
hoogte: "9"
breedte: "19"
kleur: kleur-horizontaal
][
hoogte: "19"
breedte: "9"
kleur: kleur-vertikaal
]
; bepaal voor 6-6 andere kleur
if d-index = MAX-INDEX-DOMINO [
kleur: "gold"
]
svg-domino-groep: join/with join/with join/with join/with join/with join/with
join/with join/with join/with join/with join/with svg-domino-groep
{<rect x="} to string! xco {" y="} to string! yco {" width="} breedte {" height="} hoogte {" fill="none" stroke="} kleur {" stroke-width="1" />
}
]
svg-sluit: {</svg>}
; Write the output
Either fhandle-out: try open/new file-out [
write "Schrijven naar file " write/line file-out
][
write "Kan file niet openen: "
write/line file-out
bye
]
append fhandle-out svg-start
append fhandle-out svg-text
append fhandle-out svg-text-sluit
append fhandle-out svg-domino-groep
append fhandle-out svg-sluit
close fhandle-out
Bepaal het verst afgelegen meetpunt
Hier moet een 'meetpunt geplaatst worden op zo groot mogelijke afstand van gegeven punten. Met de stelling van Pythagoras was de afstand te bepalen.
Geen programma gemaakt.
Hier kreeg je woorden die je moest plaatsen in een kolom van 15 tekens breed. 1000 punten voor elke gebruikte regel plus het kwadraat van de afsluitende aantal spaties op elke regel, behalve de laatste.
Er was geen chocola van mijn zin te maken en ChatGPT kreeg er ook geen fatsoenlijke zin uit.
Ik kon alle woorden zo plaatsen dat ze precies de kolombreedte vulden behalve voor de laatste regel, maar die overblijvende ruimte van de laatste regel telde niet mee.
Na de vierde poging even overlegd wat de bedoeling nou precies was. De gegeven volgorde aanhouden en eventueel al een woord naar de volgende regel zetten als dat in totaal 1 extra spatie zou kunnen uitmaken.
Geen programma gemaakt, opgelost met spreadsheet.
Mijn opgave, tel de grootste 3 op.
Dit is het spelletje Galaxies uit de spellenselectie van Simon Tatham dat ik op Android telefoon vaak speel. Super makkelijk dus zonder programma opgelost. Misschien een leuk idee om dat toch ooit (oooit) te maken.
Waar kan de Nemo nu zijn na het verwerken van de uitgezonden signalen?
We berekenen dit per ingevoerd signaal en verwerken zo de hele signalenlijst.
Meta [
file: "infolym-2024-2025-c1.meta"
omschrijving: {
Nemo de onderzeeer.
Oceaan, 1 is water, 0 is land, max 500x500
}
]
write/line {
C1 - Nemo.
}
let [oceaan posities nieuwe-posities] binary! 250000
change/repeat oceaan 0 250000
change/repeat posities 0 250000
change/repeat nieuwe-posities 0 250000
R-K-M: to string! read/line
space: " "
K: 0 R: 0 M: 0
sentence: R-K-M
text-left: R-K-M
while text-left [
text-left: find sentence " " ; space
forward: (count sentence ) - (count text-left)
word: copy cut sentence forward
R: K
K: M
M: to whole16! word
sentence: skip sentence forward + 1
]
;write "R=" write R write " K=" write K write " R*K=" write R * K write " M=" write/line M
for index R [
invoer: to string! read/line
kolom: 1
while 0 < count invoer [
teken: copy cut invoer 1
if teken = "." [
poke oceaan ((index - 1) * K) + kolom 1
poke posities ((index - 1) * K) + kolom 1
]
increment kolom
advance invoer
]
]
grootte: R * K
signalen: to string! read/line
while not is-empty signalen [
signaal: copy cut signalen 1
for index grootte [
if 1 = pick posities index [
if any [signaal = "N"
signaal = "?"] [
test-positie: index - K
if all [test-positie > 0
1 = pick oceaan test-positie] [
poke nieuwe-posities test-positie 1
]
]
if any [signaal = "Z"
signaal = "?"] [
test-positie: index + K
if all [test-positie <= grootte
1 = pick oceaan test-positie] [
poke nieuwe-posities test-positie 1
]
]
if any [signaal = "O"
signaal = "?"] [
test-positie: index + 1
if all [test-positie <= grootte
0 != remainder index K
1 = pick oceaan test-positie] [
poke nieuwe-posities test-positie 1
]
]
if any [signaal = "W"
signaal = "?"] [
test-positie: index - 1
if all [0 < test-positie
0 < remainder test-positie K
1 = pick oceaan test-positie] [
poke nieuwe-posities test-positie 1
]
]
]
]
for index grootte [
poke posities index pick nieuwe-posities index
]
change/repeat nieuwe-posities 0 250000
advance signalen
]
totaal: 0
for index grootte [
totaal: totaal + pick posities index
]
; Test voor inhoud van de oceaan
;write new-line write/line "De oceaan:"
oceaanstring: ""
for index R * K [
oceaanstring: join/with oceaanstring to string! pick oceaan index
if 0 = remainder index K [oceaanstring: join/with oceaanstring new-line]
]
;write/line oceaanstring
;write new-line
; Test voor inhoud van de uiteindelijke posities
positiestring: ""
for index R * K [
positiestring: join/with positiestring to string! pick posities index
if 0 = remainder index K [positiestring: join/with positiestring new-line]
]
;write/line positiestring
;write new-line write "Totaal: "
write/line totaal
BYE
We hebben ook een testscript nodig om niet alle invoer handmatig te hoeven intypen. het programma staat nu in de map 2425. De methode voor invoer is genaamd heredoc en in plaats van EOF kan ook een andere string gebruikt worden.
# test-2425-c1.sh
# testgeval 1 uitkomst 22
./2425/c1 <<EOF
5 9 7
...##....
..#.##..#
..#....##
.##...#..
....#....
WZ?OO??
EOF
# Testgeval 2 uitkomst 2
./2425/c1 <<EOF
3 3 1
.#.
..#
#..
N
EOF
# Testgeval 3 uitkomst 10
./2425/c1 <<EOF
4 4 1
...#
...#
...#
#.#.
?
EOF
Hoe dit aan te pakken is de kwestie. We kunnen niet zo makkelijk een recursieve oplossing maken als dat in andere talen kan.
Dit is nog een aardige taak. Kaj heeft de source nog wat verder geoptimaliseerd! De vraag is nog of het algoritme zelf snel genoeg is voor de gestelde limiet. Het programma doet er nog ruim 5 seconden over, de limiet is 3. Volgens mij moet er nog iets bij dat nu over het hoofd wordt gezien.
Meta [file: bereik.meta
omschrijving: {
8 < R < 17
5 < K < 12
1 < G < R + K
}
]
; Declareer en initialiseer de grid en andere lijsten
MAX-GRID-SIZE= 177
let [grid cellen stack-cel stack-keuze queue bezocht] binary! MAX-GRID-SIZE
change/repeat grid 0 MAX-GRID-SIZE
change/repeat cellen 0 MAX-GRID-SIZE
change/repeat stack-cel 0 MAX-GRID-SIZE
change/repeat stack-keuze 0 MAX-GRID-SIZE
change/repeat queue 0 MAX-GRID-SIZE
change/repeat bezocht 0 MAX-GRID-SIZE
; Stack (stack-cel, stack-keuze) bevat waarden voor cel en keuze
; Stack, queue en cel pointers bij houden
byte! [stackpointer queuepointer celpointer]
stackpointer: 0
queuepointer: 0
celpointer: 0
; Pad controle
let [linkerpad rechterpad linkerqueue rechterqueue] binary! MAX-GRID-SIZE
change/repeat linkerpad 0 MAX-GRID-SIZE
change/repeat rechterpad 0 MAX-GRID-SIZE
change/repeat linkerqueue 0 MAX-GRID-SIZE
change/repeat rechterqueue 0 MAX-GRID-SIZE
; Constante waardes
constant whole8! [
GEKLEURD= -1
LEEG
]
constant byte! [
KEUZE-0= 0
KEUZE-1
]
; Uiteraard nog geen oplossing gevonden
oplossing?: false
; Zorg dat de invoer wordt geregeld
invoer: to string! read/line
split: find/tail invoer " "
R: to byte! copy cut invoer ((count invoer) - (count split) - 1)
K: to byte! split
for index R [
invoer: to string! read/line
plaats: 1
invoer-over: invoer
while invoer-over [
invoer-over: find invoer " " ; space
verplaats: (count invoer ) - (count invoer-over)
waarde: copy cut invoer verplaats
poke grid (((index - 1) * K) + plaats) to byte! waarde
invoer: skip invoer verplaats + 1
increment plaats
]
]
laatste= R * K
laatste-rij= (to byte! R - 1) * K
K-min-1= to byte! K - 1
K-plus-1= K + 1
;
; Aanloop naar de lus
;
; Vul de cellen die gekleurd mogen worden in de oplossing in een 'cellen' rij.
cellen-index: 0
for grid-index laatste [
if 0 = pick grid grid-index [
increment cellen-index
poke cellen cellen-index grid-index
]
]
grootste-cellen-index: cellen-index
laatste-optie-cel: pick cellen grootste-cellen-index
; Start bij de eerste cel die gekleurd mag worden
cel: pick cellen 1
; Zet voor deze eerste cel de opties 0 en 1 op de stack
increment stackpointer
poke stack-cel stackpointer cel
poke stack-keuze stackpointer KEUZE-0
increment stackpointer
poke stack-cel stackpointer cel
poke stack-keuze stackpointer KEUZE-1
;
; De basis lus constructie
;
while stackpointer > 0 [
; Haal het bovenste item (cel, keuze) van de stack(s)
cel: pick stack-cel stackpointer
keuze: pick stack-keuze stackpointer
decrement stackpointer
; Pas de keuze toe op de huidige positie
either keuze = KEUZE-0 [
poke grid cel LEEG
][
poke grid cel GEKLEURD
]
; Voorwaardes
if keuze = KEUZE-1 [
; test mag niet naast al gekleurd vak restrictie
naast-gekleurd-vak?: false
kolom: remainder cel K
if any [all [cel > K
GEKLEURD = to whole8! pick grid (to byte! cel - K)
]
all [cel <= laatste-rij
GEKLEURD = to whole8! pick grid (cel + K)
]
all [kolom != 0
GEKLEURD = to whole8! pick grid (cel + 1)
]
all [kolom != 1
GEKLEURD = to whole8! pick grid (to byte! cel - 1)
] ][
naast-gekleurd-vak?: true
]
; Uitsluiten van onmogelijke combinaties, niet naast elkaar
if naast-gekleurd-vak? [
; Ongeldige toestand dus moeten we kleuren ongedaan maken
poke grid cel LEEG
; En daarna doorgaan met volgende van de stack.
continue
]
; Uitsluiten van onmogelijke combinaties, geen delen van het grid afsluiten
; Dit doen we door de paden vanuit de nieuwe cel na te gaan
; cel moet groter zijn dan K anders hoeft het nog niet
if cel > K [
; kolom: remainder cel K ; is al gedaan
rechts-aan-rand: false
links-aan-rand: false
onder-aan-rand: false
if cel > laatste-rij [onder-aan-rand: true]
if kolom = 0 [rechts-aan-rand: true
onder-aan-rand: false] ; Rechter onderhoek sluit zelf niets af
if kolom = 1 [links-aan-rand: true
onder-aan-rand: false] ; Linker onderhoek sluit zelf niets af
; check links pad naar een rand
;change/repeat linkerqueue 0 MAX-GRID-SIZE ; niet nodeloos initializeren
change/repeat linkerpad 0 laatste
linkerpointer: 0
unless links-aan-rand [
; volg het linkerpad tot einde of een rand
padcel: to byte! cel - K-plus-1
increment linkerpointer
poke linkerqueue linkerpointer padcel
while linkerpointer [
padcel: pick linkerqueue linkerpointer
decrement linkerpointer
if GEKLEURD = to whole8! pick grid padcel [
remainder-padcel-K: remainder padcel K
either any [padcel <= K
1 = remainder-padcel-K
0 = remainder-padcel-K
padcel > laatste-rij
] [
links-aan-rand: true
break
][
; Voeg toe aan gevolgd pad
if 0 = pick linkerpad padcel [
poke linkerpad padcel 1
; En voeg de cellen in de 4 richtingen toe aan de queue
increment linkerpointer
poke linkerqueue linkerpointer (padcel - K-plus-1)
increment linkerpointer
poke linkerqueue linkerpointer (padcel - K-min-1)
increment linkerpointer
poke linkerqueue linkerpointer (padcel + K-min-1)
increment linkerpointer
poke linkerqueue linkerpointer (padcel + K-plus-1)
]
]
]
]
]
;change/repeat rechterqueue 0 MAX-GRID-SIZE
change/repeat rechterpad 0 laatste
rechterpointer: 0
unless rechts-aan-rand [
; volg het rechterpad tot einde of een rand
padcel: to byte! cel - K-min-1
increment rechterpointer
poke rechterqueue rechterpointer padcel
while rechterpointer [
padcel: pick rechterqueue rechterpointer
decrement rechterpointer
if GEKLEURD = to whole8! pick grid padcel [
remainder-padcel-K: remainder padcel K
either any [padcel <= K
1 = remainder-padcel-K
0 = remainder-padcel-K
padcel > laatste-rij
] [
rechts-aan-rand: true
break
][
; Voeg toe aan gevolgd pad
if 0 = pick rechterpad padcel [
poke rechterpad padcel 1
; En voeg de cellen in de 4 richtingen toe aan de queue
increment rechterpointer
poke rechterqueue rechterpointer (padcel - K-plus-1)
increment rechterpointer
poke rechterqueue rechterpointer (padcel - K-min-1)
increment rechterpointer
poke rechterqueue rechterpointer (padcel + K-min-1)
increment rechterpointer
poke rechterqueue rechterpointer (padcel + K-plus-1)
]
]
]
]
]
if all [links-aan-rand rechts-aan-rand][
; ongeldige constructie
poke grid cel LEEG
continue
]
if all[onder-aan-rand
any [links-aan-rand
rechts-aan-rand]][
; ongeldige constructie
poke grid cel LEEG
continue
]
pad-verbonden?: false
; vergelijken linkerpad en rechterpad
testtot: to byte! cel - 2
for pad-index testtot [
test-index: to byte! testtot - pad-index + 1
if all [1 = pick linkerpad test-index
1 = pick rechterpad test-index
;cel != test-index ; dat kan niet
][
pad-verbonden?: true
break
]
]
if pad-verbonden? [
poke grid cel LEEG
continue
]
]
]
; Als we voor alle opties een keuze hebben bereikt (cel = laatste) checken
; we of dit een mogelijke oplossing is.
either cel = laatste-optie-cel [
;
; Controleer of het een oplossing is met getallen controle
; en eventueel aanvullend controle of de lege cellen met elkaar
; verbonden zijn (gebleven)
;
; Check getallen en daadwerkelijk bereik in het grid
getallen-kloppen?: true
for index laatste [
if 0 < to whole8! pick grid index [
; tel bereikbare cellen
bereik: 1
kolom: remainder index K
if kolom = 0 [kolom: K]
links: kolom - 1
i: 1
while links > 0 [
if 0 > to whole8! pick grid (to byte! index - i) [
break
]
decrement links
increment i
]
bereik: bereik + (i - 1)
if kolom = 0 [kolom: K]
rechts: K - kolom
i: 1
while rechts > 0 [
if 0 > to whole8! pick grid (index + i) [
break
]
decrement rechts
increment i
]
bereik: bereik + (i - 1)
i: 0
naar-boven: to byte! index - K
while naar-boven > 0 [
; test naar boven
if 0 > to whole8! pick grid naar-boven [
break
]
naar-boven: to byte! naar-boven - K
increment i
]
bereik: bereik + i
i: 0
naar-onder: index + K
while naar-onder <= laatste [
; test naar beneden
if 0 > to whole8! pick grid naar-onder [
break
]
naar-onder: naar-onder + K
increment i
]
bereik: bereik + i
;
if (pick grid index) != bereik [
getallen-kloppen?: false
break
]
]
;
] ; Einde FOR lus, hier gaan de breaks hierboven naar toe
;
if getallen-kloppen? [
; Als de controle op de getallen en het bereik slaagt
; dan is deze controle pas nodig
oplossing?: true
break ; naar einde WHILE lus
]
;
][ ; Alternatief van either
;
; Voeg de volgende positie en keuzes toe aan de stack
; Bepaal daarom de index van de huidige cel
for cel-index grootste-cellen-index [
if cel = pick cellen cel-index [
celpointer: to byte! cel-index
break
]
]
volgende-cel: pick cellen (celpointer + 1)
increment stackpointer
poke stack-cel stackpointer volgende-cel
poke stack-keuze stackpointer KEUZE-0
increment stackpointer
poke stack-cel stackpointer volgende-cel
poke stack-keuze stackpointer KEUZE-1
]
]
;
; Einde lusconstructie
;
;
; Uitvoer van het resultaat
;
either oplossing? [
; print het grid
uitvoer: ""
for grid-index laatste [
uitvoer: join/with join/with uitvoer to string! to whole8! pick grid grid-index " "
if 0 = remainder grid-index K [
uitvoer: join/with uitvoer new-line
]
]
][
uitvoer: "Geen oplossing mogelijk"
]
write/line uitvoer
Al deze programma's kun je (in Linux) compileren met (delen van) het volgende script. Zoals je ziet heb ik mijn scripts in een folder scripts/infolymp/ gezet. Als ik daar de source heb bewerkt kan ik het "run" script / programma gebruiken dat twee folders 'hoger' te vinden is.
# Informatica Olympiade 2024-2025
# Opgave A1
#
cd ../..
./run scripts/infolymp/infolym-2425-a1.meta
cp program.com scripts/infolymp/2425/a1
cd scripts/infolymp/infolymp/2425
./a1
#
# Opgave A2
#
cd ../..
./run scripts/infolymp/infolym-2425-a2.meta
cp program.com scripts/infolymp/2425/a2
cd scripts/infolymp/infolymp/2425
./a2
# Opgave A3
#
cd ../..
./run scripts/infolymp/infolym-2425-a3.meta
cp program.com scripts/infolymp/2425/a3
cd scripts/infolymp/infolymp/2425
./a3
# Opgave A4
#
cd ../..
./run scripts/infolymp/infolym-2425-a4.meta
cp program.com scripts/infolymp/2425/a4
cd scripts/infolymp/infolymp/2425
./a4
# Opgave A5
#
cd ../..
./run scripts/infolymp/infolym-2425-a5.meta
cp program.com scripts/infolymp/2425/a5
cd scripts/infolymp/infolymp/2425
./a5
# Opgave B1
#
cd ../..
./run scripts/infolymp/domino.meta
cp program.com scripts/infolymp/2425/b1
cd scripts/infolymp/infolymp/2425
./b1
#
# Opgave B2
# NVT
# Opgave B3
# NVT
# Opgave B4
# NVT
# Opgave C1
#
cd ../..
./run scripts/infolymp/infolym-2425-c1.meta
cp program.com scripts/infolymp/2425/c1
cd scripts/infolymp/infolymp/2425
./c1
#
# Opgave C2
#
cd ../..
./run scripts/infolymp/bereik.meta
cp program.com scripts/infolymp/2425/c2
cd scripts/infolymp/infolymp/2425
./c2